[Programmers] [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지

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

프로그래머스

이 문제는 주어진 diffs 에서 min, max 사이에서 알맞은 값의 레벨을 출력 하면 되는 문제 이다.

 

처음 문제를 구현을 했을 때는 for문을 통해 min~ max 까지 반복하면서 최솟값을 찾아 출력하는 형식으로 문제를 구현 했었다.

예제 문제는 맞추었으나, 시간초과 문제가 발생하여 구현을 다른 방식으로 하게 되었다.

 

이러한 중간 사이에 값을 맞추는 방식으로 이진 탐색 기법을 사용 하였고 

 

코드는 다음과 같다

 

def solution(diffs, times, limit):
    def can_solve_with_level(level):
        total_time = 0
        prev_time = 0
        
        for diff, time in zip(diffs, times):
            if level >= diff:
                total_time += time
            else:
                mistakes = diff - level
                total_time += mistakes * (time + prev_time) + time
            
            if total_time > limit:
                return False
            
            prev_time = time
        
        return total_time <= limit

    # 이진 탐색으로 최소 숙련도 찾기
    left, right = min(diffs), max(diffs)
    while left < right:
        mid = (left + right) // 2
        if can_solve_with_level(mid):
            right = mid  # 더 낮은 숙련도로 가능한지 탐색
        else:
            left = mid + 1  # 더 높은 숙련도가 필요
        
    return left

 

구현 과정에서 몇 가지 실수를 찾아보자면, 나는 첫 번째 문제를 틀렸을 경우 처리하는 로직을 구현하지 않았다. 아마 그래서 예제는 맞췄더라도 다른 케이스에서 틀렸던거 같다.

 

그래서 이번에는 첫 번째 문제를 틀렸을 경우 이전 문제의 난이도를 0으로 구현하여 값을 하여 계산했다.