[PCCP 기출문제] 2번 > 퍼즐 게임 챌린지 - Python, binary_search(이진 탐색)

 

 

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

프로그래머스

 

 

코드 & 풀이

 

def solution(diffs, times, limit):
    # diff <= level 일 경우 time_cur 시간 소요 후 해결
    # diff > level 일 경우 diff - level 번 틀리고, 틀릴 때마다 time_cur 소요
    # 추가로 time_prev 만큼의 시간 추가 소요해서 이전 퍼즐을 다시 풀어야 함
    # 이전 문제를 다시 풀 때는 무조건 틀리지 않음
    # 다시 풀리는 데 걸리는 시간 = (한 번 틀릴 때 걸리는 시간) * 틀린 횟수 + 이전 퍼즐로 돌아가는 시간(time_prev)
    # 한 번 틀릴 때마다 걸리는 시간 = time_cur + time_prev
    # 틀린 횟수 = diff - level
    # = (time_cur + time_prev) * (diff - level) + time_prev
    
    def find_level (level):
        new_limit = limit
        for i in range(len(times)):
            # 틀린 횟수 = diff - level
            # 한 번 틀릴 때마다 걸리는 시간 = times[i] + times[i - 1]
            mistakes = diffs[i] - level
            if mistakes <= 0: # 바로 품
                need_time = times[i]
            else:
                need_time = (times[i] + times[i - 1]) * mistakes + times[i]
            
            new_limit -= need_time
        
            if new_limit < 0:  # 제한 시간 초과 시 즉시 중단
                return False
        
        return True
    
    left, right = 1, max(diffs)
    result = right
    
    while left <= right:
        mid = (left + right) // 2
        if find_level(mid):
            result = mid
            right = mid - 1
        else:
            left = mid + 1
    
    return result

 

식은 문제에서 다 주어짐.

 

문제는 Level을 찾는 건데

 

문제는 그 Level이 어디에 있는지를 빠르게 찾는 거임

 

그래서 이진 탐색으로 최대한 탐색 시간을 줄임

 

O(log max(diffs)) => log n 이니까

 

충분함

 

 

 

 

 

 

다음에 또 봐요