[ 프로그래머스 ] [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지 (Python)

https://school.programmers.co.kr/learn/courses/30/lessons/340212

프로그래머스

 

난이도 : Level 2 
알고리즘 유형 : 이분탐색 
풀이 시간 : 38분 

문제 풀이 

제한시간 내 퍼즐을 모두 풀기 위한 숙련도(level)의 최솟값을 구하는 문제이다. 문제의 조건을 살펴보면, `diffs[i] ≤ level`인 경우, `times[i]`만큼의 시간을 사용하여 문제를 해결하고, `diffs[i] > level`인 경우에는 `(diffs[i] - level) x (times[i] + times[i - 1]) + times[i]` 만큼의 시간을 사용하여 문제를 해결한다.

 

먼저 생각할 수 있는 알고리즘은 level을 올려가며 모든 퍼즐을 탐색한 뒤, 제한시간 내 풀 수 있는 최소 level을 찾는 것이다. 하지만 각 변수의 범위를 살펴보면, $1 ≤ diffs의 길이 = times의 길이 = n ≤ 300,000$로 주어졌고, 이 말은 즉슨 최소 레벨을 찾기 위한 최악의 경우에는 $O(300,000 * 300,000)$의 시간이 소요되어 시간초과가 난다는 의미가 된다.

 

문제에서는 이전 시간 정보를 사용하기 때문에, 정렬을 사용한 그리디 알고리즘을 사용할 수도 없다. 따라서, 우리는 이분탐색 알고리즘을 사용해 최솟값을 찾아낼 수 있다.

 

결국 숙련도(level)은 난이도가 어느정도 되는지에 따라 결정이 된다. 따라서, 우리는 diffs[0]을 left로, max(diffs)를 right로 설정한 뒤, 그 중간값을 level 변수로 설정하여 모든 경우에 대해 비교해볼 수 있다.

 

만약 제한시간을 넘겼다면, 레벨을 높여주고(`left = level`), 제한시간을 넘기지 않았다면, 최솟값을 업데이트해준다(`answer = min(answesr, level`) 

 

이분탐색의 시간복잡도는 $O(logn)$이다. 따라서, 이분탐색을 사용한 본 문제의 경우 $O(nlogn)$을 갖기 때문에, 충분한 것을 확인할 수 있다.

 

코드

'''
n개의 퍼즐을 제한 시간 내에 풀어야함
난이도와 소요시간 주어짐
숙련도(level)에 따라 틀리는 횟수가 바뀜

diff <= level이면 퍼즐을 틀리지 않고 cur만큼의 시간을 사용해 해결
else, 퍼즐을 diff - level번 틀린다. 
    - 틀릴 때마다 time_cur 만큼의 시간을 사용함
    - time_prev 만큼의 시간을 사용해 이전 퍼즐을 다시 풀고와야 함
        - 이전 퍼즐을 다시 풀 떄는 틀리지 않는다.
    - 틀린 이후에 다시 퍼즐을 풀면 time_cur 만큼의 시간을 사용하여 해결한다.
    == (diff - level) x (time_cur + time_prev) + time_cur

제한시간 내 퍼즐을 모두 해결하기 위한 숙련도의 최솟값 구하기
n <= 300000
- for문을 사용해 접근하는 경우, 모든 limit까지의 경우를 탐색해야 하기 때문에 시간초과가 난다.
-> 이분탐색적으로 접근

'''

def solution(diffs, times, limit):
    answer = 0
    n = len(diffs)
    
    left, right = diffs[0], max(diffs)
    answer = right
    
    while left <= right:
        level = (left + right) // 2
        tmp = limit
        for i in range(n):
            if diffs[i] <= level:
                tmp -= times[i]
            else:
                tmp -= ((diffs[i] - level) * (times[i] + times[i - 1]) + times[i])
        # 이분탐색 체크해주기
        if tmp < 0:
            left = level + 1
        else:
            answer = min(answer, level)
            right = level - 1
    
    return answer

배운 점 

문제를 읽고, 접근을 진행할 때, 여러 알고리즘들을 떠올렸다. 하지만, 이분탐색의 경우 경험이 부족한것인지 모르겠지만 빠르게 떠오르지 않았다.

정렬이 불가능하고, 이전 결과에 영향을 주는 상태에서 무언가의 최솟값을 찾는 경우라면 이분탐색 알고리즘을 빠르게 생각해낼 수 있도록 꾸준히 문제를 풀어야겠다.