[프로그래머스][PCCP 기출] 퍼즐게임 챌린지

1. 문제

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

 

2. 코드

python 1

def solution(diffs, times, limit):
    low = 1
    high = max(diffs)
    answer = high
    
    while low <= high :
        mid = (low + high) // 2
        total_time = 0
        
        for i in range(len(diffs)):
            if total_time > limit: break
            
            # diff <= level -> time_cur만큼 시간 사용
            if diffs[i] <= mid: total_time += times[i]

            # diff > level -> diff-level 틀림, time_cur만큼 시간 이용 추가로 time_prev 만큼 시간을 사용
            elif diffs[i] > mid: 
                wrong = diffs[i] - mid
                total_time += (times[i] + times[i-1]) * wrong + times[i]
        
        if total_time <= limit:
            answer = mid
            high = mid - 1
        else:
            low = mid + 1
            
            
    return answer

풀이

1. 최솟값, 최댓값의 범위를 정함 → level의 값을 찾기 위함
2. level의 범위를 이진 탐색으로 반씩 줄여가며 최소 level 찾음
3. 총 시간 계산
   1. 현재 숙련도 = mid
   2. 숙련도가 충분하면 → 바로 시간 합산
   3. 숙련도가 충분하지 않으면
   4. → (현재 소요시간 + 이전 소요시간) * 틀린 개수 + 현재 소요시간 합산
4. total 시간 ≤ limit → 현재 숙련도로 가능하므로 answer갱신 high를 줄임
5. total 시간 > limit → 현재 숙련도로 불가능하므로 low를 늘림
6. 최종적인 최소 숙련도(level) 출력

 

3. 메모

• 시간 복잡도: O(NlogM)
• 문제를 보면 단조성이 있음 → 이진탐색을 쓸 수 있는 후보임숙련도가 커질수록 문제를 덜 틀림 → 걸리는 시간이 같거나 줄어듬
• 단조성?
• 단순 순차 탐색은 시간 초과 됨
  • 최선의 경우 시간 복잡도: O(N)
  • 최악의 경우 시간 복잡도: O(N * max(diffs))