[Programmers] PCCP 기출문제 2번 - 퍼즐 게임 챌린지

문제 분석

• n개의 퍼즐을 제한시간 안에 풀어야하는 퍼즐 게임을 수행.
• 현재 퍼즐의 난이도가 diff, 현재 퍼즐을 푸는데 소요되는 시간이 time_cur, 이전 퍼즐 소요 시간이 time_prev일 때
  • diff <= level인 경우, time_cur만큼의 시간만 소요하여 해당 문제를 해결할 수 있음.
  • diff > level인 경우, diff-level만큼 퍼즐을 틀림. 퍼즐을 틀릴 때, time_cur + time_prev만큼의 시간이 추가로 소요되며, 이전 퍼즐로 돌아가서 문제를 해결할 때는 level에 상관없이 무조건 문제를 해결.
  • diff-level만큼의 시간이 지나면 time_cur만큼의 시간을 소요하여 다음 단계로 넘어갈 수 있음.
• 전체 제한시간 limit이 정해져 있으며, 정해진 제한시간 내에 퍼즐을 모두 해결하기 위한 level의 최솟값을 Return하는 문제.

 

문제 접근

• 퍼즐의 난이도와 소요 시간이 저장되어 있는 배열 diffs, times의 길이가 1 ~ 30만이기 때문에, O(n**2)로 접근하여 문제를 해결하게 되면 시간 복잡도 측면에서 Time Limit이 발생할 수 있음.
• level을 어떻게 효율적으로 탐색할까?
  • 하한선 = diffs[0]은 항상 1이기 때문에, level이 1인 경우가 하한선.
  • 상한선 = max(diffs)이며, 최댓값보다 level이 큰 경우 최댓값일 때와 항상 동일한 time이 소요되기 때문에 max(diffs)가 상한선.
  • 하한선과 상한선이 명확하게 주어져있는 상황이라면 이분 탐색을 활용하여 효율적으로 탐색이 가능할 것이라 생각함.
  • 배열 원소의 범위가 1 ~ 10만일 때 이분 탐색을 사용하여 level을 탐색한다면, O(log 100000) => 대략 16 ~ 17사이의 값을 바탕으로 찾고자 하는 level 값을 찾을 수 있음.
  • diffs 길이가 N이고, diffs[0]의 K라 할 때, 해당 문제는 O(N) * O(log K)로 해결 가능

 

소스 코드

def solution(diffs, times, limit):
    answer = 0
    l, r, length = 1, max(diffs), len(diffs)
    while l <= r:
        level = (l+r)//2
        total_time = times[0]
        for i in range(1, length):
            total_time += times[i]
            if diffs[i] > level:
                total_time += (diffs[i]-level)*(times[i-1]+times[i])
        if total_time <= limit:
            r = level-1
            answer = level
        else:
            l = level+1
    return answer