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

 문제

 

코딩테스트 연습 - [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지 | 프로그래머스 스쿨

 

 

풀이

 

💡 입력들의 범위를 살펴보자

1 ≤ diffs의 길이 = times의 길이 = n ≤ 300,000
1 ≤ diffs[i] ≤ 100,000
1 ≤ times[i] ≤ 10,000
1 ≤ limit ≤ 10^15

 

level 값의 범위가 되는 diffs 배열의 크기가 100,000이었기 때문에 O(n log n)으로 풀어야겠다고 생각했다.

이제서야 좀 시간복잡도 관련된 지능이 생긴 것 같다.

특정 범위 안에서 '숙련도의 최솟값'을 찾는 문제라서 이분 탐색을 바로 떠올렸다.

(백준에서 여러 번 탐독한 보람이 있었따 v)

 

 

풀다 보니 "퍼즐을 틀릴 때마다, time_cur만큼의 시간을 사용하며, 추가로 time_prev만큼의 시간을 사용해 이전 퍼즐을 다시 풀고 와야 합니다."라는 거지 같은 조건이 있었다. 

 

 

그래서 처음에는 start 값을 무조건 min(diffs)+1로 두고 가장 난이도가 쉬운 문제는 무조건 푼다는 방향으로 잡았는데, 그러면 times 접근 시에도 min(diffs)에 대한 인덱스 값을 고려해줘야 되는 점이 이상해서 다시 생각했다.

 

 

입출력 예시를 뜯어보니 문제를 제대로 안 읽었던 것

제한 조건에도 떡하니 diffs[0] = 1 라고 기재되어 있음을 뒤늦게 발견했다.

 

고로? 첫 번째 문제는 무조건 푼다 = times[0]를 초기 값으로 둔다.

time_prev만큼의 시간을 사용해 이전 퍼즐을 다시 풀어야 할 때 인덱스 값을 1부터 접근해 indexOutOfRange 에러를 막는다

 

 

 

import sys

def solution(diffs, times, limit):
    answer = sys.maxsize
    start = min(diffs)
    end = max(diffs)
    # mid는 level을 뜻함
    while start <= end:
        mid = (start+end)//2
        time_sum = times[0] # diffs[0] = 1이기 때문에 첫 문제는 무조건 푼다고 가정
        for i in range(1, len(diffs)):
            if diffs[i] <= mid:
                time_sum += times[i]
            else:
                add_time = (times[i]+times[i-1])*(diffs[i]-mid) + times[i]
                time_sum += add_time
        
        # 이분탐색 진행
        if time_sum <= limit: # 제한시간 안에 충분하게 풀었다
            answer = min(answer, mid)
            end = mid-1 # 숙련도 낮춰서 최솟값 탐색
        else:
            start = mid+1
        
    return answer