프로그래머스

프로그래머스 퍼즐 게임 챌린지 풀이: 이분 탐색으로 최소 숙련도 찾기

작성자: solve together · 작성 언어: Python

0. 문제 링크와 출처

한 숙련도를 정했을 때 모든 퍼즐을 제한 시간 안에 풀 수 있는지 계산하고, 가능한 숙련도 중 최솟값을 찾아야 합니다. 숙련도가 높아질수록 실패 횟수가 줄어드는 구조와 최대 입력 크기를 함께 고려해야 하므로 Level 2로 판단했습니다.

문제 원문과 제한 조건은 변경될 수 있으므로 제출 전에는 공식 문제 페이지를 다시 확인하세요.

1. 문제 요약

각 퍼즐에는 난이도 diffs[i]와 기본 풀이 시간 times[i]가 있습니다. 현재 숙련도 level이 퍼즐 난이도보다 낮으면 다음 시간만큼 소요됩니다.

실패 횟수 = diffs[i] - level
소요 시간 = times[i] + 실패 횟수 × (times[i] + 이전 퍼즐 시간)

첫 번째 퍼즐은 이전 퍼즐이 없으므로 항상 diffs[0] = 1인 조건을 이용해 기본 시간만 더합니다. 전체 소요 시간이 limit 이하가 되는 최소 숙련도를 구합니다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

핵심 관찰

숙련도가 1 증가하면 난이도가 숙련도보다 높은 퍼즐의 실패 횟수가 줄어들거나 그대로 유지됩니다. 따라서 숙련도가 높아질수록 전체 소요 시간은 증가하지 않습니다.

이 단조성을 이용하면 숙련도를 1부터 모두 확인할 필요 없이, 1부터 가장 높은 퍼즐 난이도까지 이분 탐색할 수 있습니다. 특정 숙련도로 제한 시간 안에 풀 수 있다면 더 낮은 숙련도도 확인하고, 시간이 초과되면 더 높은 숙련도를 확인합니다.

시간 판정 함수

can_finish(level) 함수는 퍼즐을 순서대로 확인하며 총 소요 시간을 계산합니다. 현재 퍼즐의 난이도가 숙련도보다 높은 경우에만 실패 시간 공식을 적용합니다. 총 시간이 limit를 초과하면 남은 퍼즐을 확인하지 않고 즉시 False를 반환할 수 있습니다.

3. 문제 해결 코드 (Python)

def solution(diffs, times, limit):
    def can_finish(level):
        total = times[0]

        for i in range(1, len(diffs)):
            mistakes = max(0, diffs[i] - level)
            total += times[i] + mistakes * (times[i] + times[i - 1])

            if total > limit:
                return False

        return True

    left, right = 1, max(diffs)

    while left < right:
        level = (left + right) // 2

        if can_finish(level):
            right = level
        else:
            left = level + 1

    return left

can_finish 한 번은 모든 퍼즐을 최대 한 번 순회하므로 O(n)입니다. 숙련도 범위의 크기는 최대 100,000이므로 이분 탐색을 포함한 시간 복잡도는 O(n log D)입니다. 여기서 D는 가장 높은 퍼즐 난이도이며, 추가 공간 복잡도는 O(1)입니다.

4. 오답 접근과 반례

숙련도를 1부터 증가시키며 매번 전체 퍼즐을 확인하면 결과는 구할 수 있지만, 숙련도 후보마다 O(n) 순회를 반복합니다. n = 300,000이고 난이도 범위가 큰 경우 불필요한 반복이 많아집니다.

또한 실패 횟수만 times[i]와 곱하면 이전 퍼즐을 다시 푸는 시간이 빠집니다. 예를 들어 현재 퍼즐의 난이도가 3, 숙련도가 1, 현재 시간이 2, 이전 시간이 4라면 실패 2회의 시간은 2 × (2 + 4) + 2 = 14입니다. 2 × 2 + 2 = 6으로 계산하면 오답입니다.

5. 공식 예제와 추가 검증

공식 예제 4개를 Python 3.12.4에서 실행했고 모두 기대값과 일치했습니다.

예제 기대 출력 확인 결과
1 3 통과
2 2 통과
3 294 통과
4 39354 통과

추가 검증 1: 퍼즐이 하나뿐인 경우

입력: diffs=[1], times=[5], limit=5
기대 출력: 1
확인 결과: 통과
검증 목적: 이전 퍼즐 시간이 없는 최소 입력 확인

추가 검증 2: 숙련도 1로도 제한 시간에 도달하는 경우

입력: diffs=[1, 2], times=[1, 1], limit=3
기대 출력: 1
확인 결과: 통과
검증 목적: 가능한 최소 숙련도 반환 확인

추가 검증 3: 최고 난이도까지 필요한 경우

입력: diffs=[1, 10], times=[2, 3], limit=5
기대 출력: 10
확인 결과: 통과
검증 목적: 최고 난이도가 정답이 되는 이분 탐색 경계 확인

6. 다른 풀이 방식 검색 및 비교

공개된 풀이들도 이 문제의 단조성을 이용해 이분 탐색을 사용합니다. 이 글에서는 판정 함수에서 제한 시간을 넘는 즉시 순회를 중단하고, 첫 퍼즐은 별도로 처리해 이전 퍼즐 시간이 없는 조건을 코드에 명확히 반영했습니다.

마무리

이 문제는 숙련도 자체를 직접 최적화하기보다, 특정 숙련도로 제한 시간 안에 완료할 수 있는지를 먼저 판정하는 문제로 바꾸면 간단해집니다. 가능 여부가 숙련도에 대해 단조롭게 변하므로 이분 탐색으로 최소 숙련도를 찾을 수 있습니다.

#이분탐색#프로그래머스#난이도 2