[프로그래머스-파이썬] 퍼즐게임 챌린지

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

 

 

일단 논리를 만드는 것 자체가 어렵다기 보단 시간초과 나지 않도록 만드는 게 어렵다.

가장 먼저 시간초과 나지만 값은 맞는 버전의 코드를 보자.

def solution(diffs, times, limit):
    answer = 0
    n = len(diffs)
    
    level = max(diffs)
    spend = limit
    
    while spend<=limit:
        # spend 계산
        temp = 0
        if diffs[0]> level:
            temp = (diffs[0]-level)*times[0]
        else:
            temp = times[0]
        
        for i in range(1, n):
            if diffs[i] > level:
                temp+= (diffs[i]-level) * (times[i] +times[i-1]) + times[i]
            else:
                temp+= times[i]
        
        if temp == spend:
            break
        
        level -= 1
        spend = temp
        
    answer = level+2
    return answer

 

level을 1씩 줄여나가기 때문에 시간 복잡도가 최대 O(N+M)이다. 그리고 왠지 이유는 못찾았는데 +2를 해줘야 정답이다. 안해줬더니 모든 테케에서 2씩 작은 값이 나왔었음 ㅠ 이유를 아직 모르겠다. 그래서 지피티한테 물어봤다.

 

while 루프 안에서 level을 감소시키고 spend를 재계산한 후 탈출하기 때문에,
탈출 시점의 level은 실제로 가능한 최소 레벨보다 두 단계 낮아져 있습니다.
그래서 answer = level + 2로 보정해야 올바른 정답이 됩니다.

 

그렇다고 합니다. 자세한 설명은 문제 링크랑 위 코드를 붙여넣기 해서 물어보면 길고 상세하게 설명해준다.

 

def solution(diffs, times, limit):
    answer = 0
    n = len(diffs)
    
    low = 0
    high = max(diffs)
    
    while low<=high:
        mid = (low+high)//2
        
        # spend 계산
        temp = 0
        if diffs[0]> mid:
            temp = (diffs[0]-mid)*times[0]
        else:
            temp = times[0]
        
        for i in range(1, n):
            if diffs[i] > mid:
                temp+= (diffs[i]-mid) * (times[i] +times[i-1]) + times[i]
            else:
                temp+= times[i]
        
        
        if temp <= limit:
            high = mid -1
        else:
            low = mid +1
        
        
    answer = low
    if answer <=0:
        answer = 1
    return answer

 

최종 코드는 결국 이분탐색으로 풀었다.

이 코드를 짜면서 14번 테케만 자꾸 틀렸는데 그 이유가 조건에 "난이도, 소요 시간은 모두 양의 정수며, 숙련도도 양의 정수여야 합니다."라고 되어있기 때문이다. 14번 테케는 양의정수가 아닌 answer가 0인 경우이므로 이런 경우를 방지하고자 마지막에 if 문 한 줄 더 추가했더니 정답이 되었다.

 

역시 코테는 섬세해..