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

문제

 

풀이

 

문제 자체는 간단했다.

난이도 배열을 돌며 현재 레벨보다 난이도가 낮을 때와 높을 때를 나누어 시간을 계산해주고,

더한 시간이 limit보다 낮을 경우의 level의 최솟값을 구하면 되는 문제.

 

나는 난이도 배열을 돌며 시간을 계산하는 함수를 만들었고, 해당 함수에 level만 바꾸어 넣어주며

정답을 구했다.

 

코드

첫번째 (틀린) 코드

시간초과가 난 코드이다

def solution(diffs, times, limit):
    answer = 1
    
    # 작은 수부터 level 설정해서 계산
    while(True):
        if puzzle(answer,diffs,times,limit):
            break
        answer += 1
    
    return answer

def puzzle(level,diffs,times,limit):
    n = len(diffs)
    time_cur = 0
    time_prev = 0
    total_time = 0
    
    for i in range(n):
        time_cur = times[i]          
        # 1. diff > level이면 (diff-level)*(time_cur+time_prev)+time_cur
        if diffs[i] > level:
            total_time += (diffs[i]-level)*(time_cur+time_prev)+time_cur   
        # 2. diff <= level이면 time_cur만큼의 시간만 사용 
        else:
            total_time += time_cur
        time_prev = times[i]    
    
    if total_time <= limit:
        return True
    else:
        return False

 

while문 내에서 level의 값을 1씩 올리면서 검사를 했기 때문에 발생한 문제이다.

내가 만든 퍼즐 함수의 시간복잡도는 최악의 경우 diffs의 길이만큼 for문을 돈다.
(시간복잡도 O(n), 각 원소에 대해 시간을 계산해야하기 때문)

주어진 난이도의 원소의 최대 값이 100,000이므로 while문을 많이 돌리면 함수 내의 for문도 많이 돌아

시간복잡도가 오버될 수 밖에 없었다.

 

제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 구하는 문제이므로 정답 level은

diffs의 최댓값을 넘지 않는다.

따라서 이 점을 이용해 level의 값을 이분탐색으로 찾아보려고 했다.

 

정답 코드

def solution(diffs, times, limit):
    answer = 1
    left = 1
    right = max(diffs)
    
    while left <= right:
        mid = (left + right) // 2
        # 조건에 맞으면 더 작은 level값이 있는지 탐색
        if puzzle(mid,diffs,times,limit):
            right = mid - 1
            answer = mid
        # 조건에 맞지 않으면 level의 값 늘리기
        else:
            left = mid + 1
    return answer

def puzzle(level,diffs,times,limit):
    n = len(diffs)
    total_time = 0
    time_cur = 0
    time_prev = 0
    
    for i in range(n):
        time_cur = times[i]          
        # 1. diff > level이면 (diff-level)*(time_cur+time_prev)+time_cur
        if diffs[i] > level:
            total_time += (diffs[i]-level)*(time_cur+time_prev)+time_cur   
        # 2. diff <= level이면 time_cur만큼의 시간만 사용 
        else:
            total_time += time_cur
        time_prev = times[i]    
    
    return total_time <= limit

 

이분탐색을 사용해 level의 값을 탐색했다.

이분탐색을 할 때, left의 값은 0이 아닌 1에서 시작해야한다. (테스트케이스 14번이 틀리는 이유이다)

 

그리고 퍼즐 함수의 리턴값을 변경했다.

total_time <= limit를 리턴함으로서 코드의 가독성을 높였다.

 

 

 

프로그래머스