[Python 파이썬] 프로그래머스 - [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지

2024년 9월 24일

문제 링크 : 프로그래머스 - [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지

---

문제 접근

 
현재 나의 숙련도에 따라 퍼즐을 푸는 시간이 달라진다.
 
diffs의 각 요소는 최대 100000이므로, 나의 숙련도는 1 ~ 100,001일 것이다.
 
1 부터 100,001 까지 일일이 확인해보기엔 시간복잡도 측면에서 좋을 게 없다.
(퍼즐의 개수 n의 최대 값은 300,000 이므로, 최악의 경우 100,001 * 300,000 ~= 10^10번 연산해야 한다.)
 
그러므로 우리는 효율적으로 숙련도의 최소값을 찾아야 한다. 어떻게? 이분 탐색으로!
 

---

내가 가질 수 있는 숙련도의 범위는 1 ~ 100,001 이므로 양 끝 값인 left, right는 각각 1, 100,001로 초기화 시켜준다.
left와 right의 중앙값 mid를 현재 숙련도로 가정하고 모든 퍼즐을 수행할 때 제한 시간 내에 풀 수 있는지, 그러지 못하는지에 따라 mid 값을 변동시켜주면 된다.
 
참고로 문제에서 요구하는, 난이도에 따른 퍼즐 풀이 소요 시간은 코드로 표현하면 다음과 같다.
(mid는 숙련도 이다.)

# diff ≤ level이면 퍼즐을 틀리지 않고 time_cur만큼의 시간을 사용하여 해결합니다.
now_spend_time += times[idx]

# diff > level이면, 퍼즐을 총 diff - level번 틀립니다. 
# 퍼즐을 틀릴 때마다, time_cur만큼의 시간을 사용하며, 추가로 time_prev만큼의 시간을 사용해 이전 퍼즐을 다시 풀고 와야 합니다. 이전 퍼즐을 다시 풀 때는 이전 퍼즐의 난이도에 상관없이 틀리지 않습니다. diff - level번 틀린 이후에 다시 퍼즐을 풀면 time_cur만큼의 시간을 사용하여 퍼즐을 해결합니다.
now_spend_time += ((times[idx] + times[idx - 1]) * (diffs[idx] - mid) + times[idx])

 
제한 시간 내에 퍼즐을 풀지 못했다면 숙련도가 너무 낮기 때문이므로 left 값을 mid + 1로 치환해 중앙값 mid를 증가시켜주고,
제한 시간 내에 퍼즐을 풀었다면,  숙련도의 최소값을 찾기 위해 숙련도를 더 낮춰볼 필요가 있다. 그러므로 right 값을 mid로 치환해 중앙값 mid를 감소시켜준다.
 
이 작업을 반복하다보면 left가 right보다 크거나 같아지는 경우가 생긴다. 이 때 반복문을 종료하고 마지막 right 값을 출력해주면 문제에서 원하는 숙련도의 최소값이 된다.
 
 

---

전체 코드

 

def solution(diffs, times, limit):
    # diffs[i]의 최대값 : 100000
    left = 1
    right = 100001

    # 퍼즐의 개수 n
    n = len(diffs)

    while left < right:
        # mid : 현재 숙련도
        mid = (left + right) // 2
        # 현재 숙련도로 소요한 시간
        now_spend_time = 0
        # 제한 시간을 넘었는지 체크
        is_timeover = False

        for idx in range(n):
            if mid >= diffs[idx]:
                now_spend_time += times[idx]
            else:
                now_spend_time += ((times[idx] + times[idx - 1]) * (diffs[idx] - mid) + times[idx])

            if limit < now_spend_time:
                is_timeover = True
                break

        if is_timeover:
            left = mid + 1
        else:
            right = mid

    return right

if __name__ == "__main__":
    diffs = [1, 328, 467, 209, 54]
    times = [2, 7, 1, 4, 3]
    limit = 1723

    print(solution(diffs, times, limit))

---

풀이 후기

 
이분 탐색 문제는 대부분 문제가 다음과 같은 방향으로 주어진다.
 

특정 수치를 다르게 할 때마다 어떤 결과값이 변동된다.

결과값이 특정 조건(어떤 제한에 근접하거나, 제한 내에 이루어지거나 등등...)에 맞도록 수치를 조정할 것이다.

특정 수치의 최소 or 최대값을 찾고 싶다.

 
완전 탐색으로 풀면 보통 시간초과를 피할 수 없는 문제로 입력 값들의 스케일이 주어지기에 이런 느낌의 문제라면 이분 탐색을 의심해보는게 좋다.