[Programmers] - Python / 파이썬 - 퍼즐 게임 챌린지

문제

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

시간 복잡도

• n만큼의 반복 + 이분탐색 범위(m) -> $O(n \log m)$
• n의 최대값은 300,000이고 m의 최대 범위는 100,000이기 때문에 시간은 충분하다.
• $\log 100,000$ 의 값은 약 17이다.

문제 접근법

• 이분탐색

1. diffs에서 가장 작은 값과 가장 큰 값을 각각 이분탐색의 시작, 끝 범위로 정한다.
2. 이분탐색을 시작한다.
   2-1. 중간값을 구한다. -> 현재 레벨
   2-2. 현재 레벨로 모든 퍼즐의 수행 시간을 나타낼 변수를 정의한다.
   2-3. 모든 퍼즐을 탐색한다.
   ㅤㅤ2-3-1. 이전 퍼즐 시간은 현재 퍼즐의 인덱스가 0인 경우는 0, 나머지는 현재 인덱스 이전의 시간으로 정한다.
   ㅤㅤ2-3-2. 문제의 조건에 맞게 현재 퍼즐과 현재 난이도에 맞는 수행 시간을 모두 더한다.
   2-4. 현재 모든 퍼즐의 수행 시간이 제한 시간보다 큰 경우, 현재 레벨을 정답으로 설정 후 이분탐색의 끝 범위를 중간값 - 1로 해준다.
   ㅤㅤ-> 최소 레벨을 구해야 하기 때문에, 제한 시간을 넘지 않으면 레벨을 점점 줄여나간다.
   2-5. 현재 모든 퍼즐의 수행 시간이 제한 시간보다 작은 경우, 이분탐색의 시작 범위를 중간값 + 1로 해준다.
3. 레벨을 출력한다.

코드

# Programmers
# Lv.2 - 퍼즐 게임 챌린지

def solution(diffs, times, limit):
    start, end = min(diffs), max(diffs)
    level = 0
    
    while start <= end:
        mid = (start + end) // 2
        total = 0
        
        for i in range(len(diffs)):
            time_prev = times[i - 1] if i else 0
            total += (diffs[i] - mid) * (times[i] + time_prev) + times[i] if diffs[i] > mid else times[i]
            
        if total <= limit:
            level = mid
            end = mid - 1
        else:
            start = mid + 1

    return level