(Python) 프로그래머스 - 퍼즐 게임 챌린지

프로그래머스에 새로운 문제가 올라왔길래 오랜만에 풀어보았다.

최초에는 완전탐색으로 접근하면 시간초과가 나는걸 알면서도 다른 로직이 안떠올라서 일단 완전탐색으로 구현하고

이진탐색으로 수정해서 풀이에 성공했다.

 

---

로직

배열의 크기가 300,000 이므로 완전 탐색으로 접근하면 100% 시간 초과가 난다.

여기서 이진 탐색을 떠올려야 하는데, level의 최댓값이 diffs 요소중 가장 큰 값이라는걸 캐치해서 풀어야 한다.

그러므로 1 <= level의 최솟값 <= diffs 요소의 최댓값이 된다.

이진탐색으로 level의 값들을 cal 함수에 넣어주면서 탐색하면 최종적으로 level의 최솟값이 나오게 된다.

 

cal 함수에서는 제한시간을 넘으면 탐색을 중지하고 False를 반환하고, 제한시간안에 모든 탐색을 끝냈다면 True를 반환한다. cal 함수의 반환 결과에 따라 이진탐색과정을 반복한다.

 

최종 코드

def solution(diffs, times, limit):
    answer = 0

    left = 1
    right = max(diffs)

    while left <= right:
        mid = (left + right) // 2

        if cal(diffs, times, limit, mid):
            answer = mid
            right = mid - 1
        else:
            left = mid + 1

    return answer


def cal(diffs, times, limit, level):
    time_added = 0
    
    for i in range(len(diffs)):
        diff = diffs[i]
        time_cur = times[i]
        time_pre = 0
        if i != 0:
            time_pre = times[i - 1]

        if diff <= level:
            time_added = time_added + time_cur
        else:
            re_cnt = diff - level
            re_cal = time_pre + time_cur
            cal_time = re_cnt * re_cal + time_cur
            time_added = time_added + cal_time

        if time_added > limit:
            return False

    return True