프로그래머스

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

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

한 숙련도를 정했을 때 모든 퍼즐을 제한 시간 안에 풀 수 있는지 계산하고, 가능한 숙련도 중 최솟값을 찾아야 한다. 판정 함수의 단조성을 파악하고 이분 탐색을 적용해야 하므로 Level 3으로 판단했다.

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으로 계산하면 오답이다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 최소 숙련도와 최고 난이도 경계를 확인할 수 있다.

assert solution([1], [5], 5) == 1
assert solution([1, 2], [1, 1], 3) == 2
assert solution([1, 10], [2, 3], 5) == 10

5. 공식 예제와 추가 검증

공식 예제 4개의 기대 출력과 함께, 아래 경계 테스트 세 입력을 Python 3.10.5에서 실행해 기대값과 일치하는지 확인했다.

예제 기대 출력
1 3
2 2
3 294
4 39354

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

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

추가 검증 2: 첫 번째 퍼즐에서 실패 시간이 추가되는 경우

입력: diffs=[1, 2], times=[1, 1], limit=3
기대 출력: 2
확인 결과: 통과
검증 목적: 첫 퍼즐은 기본 시간만 들지만 다음 퍼즐은 실패 시간까지 계산하는지 확인

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

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

6. 참고 풀이 비교

  • syrbear의 풀이는 숙련도 후보를 이분 탐색하고 각 후보의 총 소요 시간을 순회하는 접근을 설명한다.

이 글에서는 판정 함수에서 제한 시간을 넘는 즉시 순회를 중단하고, 첫 퍼즐은 별도로 처리해 이전 퍼즐 시간이 없는 조건을 코드에 명확히 반영했다.

마무리

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

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