[Python] 프로그래머스 퍼즐 게임 챌린지

1. 문제 - 프로그래머스 퍼즐 게임 챌린지 (PCCP 기출 문제)

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

 

💡알고리즘 - 파라메트릭 서치(이분 탐색을 이용한 조건에 맞는 값 찾기)

- for문으로 1부터 시작하여 문제 조건에 맞는 숙련도(level)을 찾게 도면, diffs 와 times의 길이는 최대 300,000이고
diffs는 최대 100,000 이기 때문에 시간복잡도 O(n^2)에 의해 시간초과가 발생한다.

- 이럴때 탐색에 있어 시간을 줄여줄 방법론들을 생각해봐야한다. 이분탐색? 투포인터?

- 문제에서 diffs[0]는 1로 고정되어있다. 즉, diffs의 최소, 최대값이 명확하며 특정 조건을 만족하는 level의 최소값을 찾는거라면
"파라메트릭 서치"를 떠올릴 수 있다.

 

✅ 풀이

def solution(diffs, times, limit):
    start = 1
    end = max(diffs)
    answer = 0
    
    def calculate(level):   # level 별로 문제들을 푸는데 드는 총 소요 시간을 계산하는 함수
        sum_time = 0
        
        for i, (diff, time) in enumerate(zip(diffs, times)):
            if diff <= level:
                sum_time += time
            else:
                sum_time += (diff - level) * (times[i-1] + time) + time
                # times[i-1]: 이전 퍼즐을 푸는 데 소요되는 시간 = time_prev
                # time: 현재 퍼즐을 푸는 데 소요되는 시간 = time_cur
                
        return sum_time
    
    while start <= end:
        mid = (start + end) // 2
        
        if calculate(mid) <= limit:
            end = mid - 1
            answer = mid
        else:
            start = mid + 1

    return answer

 

- calculate(level) 함수는 문제 조건에 맞게 level 별로 퍼즐을 푸는 총 시간을 계산하는 함수이다.

def solution(diffs, times, limit):
    start = 1
    end = max(diffs)
    answer = 0
    
    while start <= end:
        mid = (start + end) // 2
        
        if calculate(mid) <= limit:
            end = mid - 1
            answer = mid
        else:
            start = mid + 1

    return answer

 

- 이부분이 이분 탐색을 활용한 파라메트릭 서치를 진행하는 부분이다.

start를 최소값인 1로 잡고, end를 최대값인 max(diffs)로 잡고 그 안에서 이분탐색을 진행한다.

- 총 시간이 limit 이내라면 값을 만족하는 level의 최소값이 될 수 있는 후보중 하나이므로 answer = mid로 저장해두고, 값을 더 줄여보기 위해 end = mid - 1로 설정한다.

- 총 시간이 limit을 넘는다면 level 값의 범위를 더 크게 잡아봐야하므로, start = mid + 1을 통해 더 큰 값으로 범위를 잡는다.