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

728x90

PCCP 기출문제 2번 - 퍼즐 게임 챌린지

문제설명

본 문제는 난이도와 해결 시간이 주어진 퍼즐들을

제한 시간내에 해결할 수 있는 최소 숙련도 (level)을 구하는 문제이다.

여기 level이란, 퍼즐의 난이도와 같은 의미로 보면 된다.

본 문제의 입력은 총 3가지이다.

문제의 난이도를 갖고 있는 배열 diffs

각 문제를 해결하는 데에 걸리는 시간들의 배열 times

문제 해결을 위한 제한시간 limit

각 변수들 사이의 상관관계는 문제를 해결하는 시간에 있다.

문제를 해결하는 시간을 구하는 방법은 아래와 같다.

level 보다 난이도가 높은 문제에 대해선, diff - level 만큼 실수하게 된다.

이 때, 각 실수는 (이전 퍼즐의 시간 + 현재 퍼즐의 해결 시간) 만큼의 시간이 추가 소요되며

실수 후에 퍼즐을 해결하기 위한 time이 추가 소요된다.

또한 level 보다 낮거나 같은 난이도의 모든 문제는 time만큼의 시간을 소요하여 퍼즐을 해결할 수 있다.

이렇게 경우의 수를 살펴서 최소 숙련도를 구하면 된다.

제한사항

제한 사항을 보면 문제의 개수는 30만개이다.

간단히 어림짐작해도 시간이 조금 부족할 수도 있음을 고려한 알고리즘을 활용해야 될 것으로 보인다.

문제풀이

앞서 문제를 이해하는 과정에서 알 수 있듯, 본 문제는 최적의 level을 구하는 문제이다.

그 과정에서 알 수 있는 점은 숙련도가 낮을 경우 퍼즐을 여러번 틀리게 되며, 이 때 시간이 더욱 소모되고

숙련도가 높을 경우 점점 적은 시간을 사용하게 된다.

(즉, 총 걸리는 시간과 숙련도는 반비례 관계에 있다.)

하지만, 모든 숙련도에서 나올 수 있는 경우의 수를 탐색하기엔,

시간이 터무니 없이 부족하다. (입력 배열 크기가 30만개)

이 정도 내용을 읽으면 어느정도 머리에 그려졌을 텐데,

해당 문제는 이진탐색 알고리즘으로 쉽게 해결할 수 있다.

추가적으로 본인은 14번 테스트 케이스에서 여러번 시행착오를 겪었는데,

해당 예외 케이스 같은 경우, diff가 [1, 2]와 같이 주어지는 경우,

반드시 0으로 반환하는 문제였다.

이는 문제의 설명을 제대로 읽지 않아서 발생한 문제이다.

모든 값은 양수이다.

이를 이해하면 문제를 쉽게 해결해볼 수 있다.

정답코드

def solution(diffs, times, limit):
    # 퍼즐의 난이도와 소요 시간을 묶어줌
    puzzles = list(zip(diffs, times))
    
    start, end = 0, max(diffs)  # 이진 탐색 범위 (숙련도는 난이도 중 가장 큰 값까지 가능)
    last_cur = 0 # 마지막 숙련도 저장
    
    # 이진 탐색 시작
    while start <= end:
        total_times = 0
        cur = (start + end) // 2  # 중간 숙련도
        
        # 현재 숙련도로 각 퍼즐을 풀 때의 시간을 계산
        for i, (diff, time) in enumerate(puzzles):
            if cur < diff:  # 숙련도가 부족하여 틀릴 때
                if i > 0:
                    total_times += (times[i-1] + time) * (diff - cur)
                else:
                    total_times += time * (diff - cur)
            total_times += time  # 기본적으로 소요 시간 추가
        
        # 계산된 시간과 제한 시간을 비교
        if total_times <= limit:  # 제한 시간 내에 해결 가능하면 숙련도 낮춰보기
            last_cur = cur  # 최적 숙련도 갱신
            end = cur - 1
        else:  # 제한 시간을 넘기면 숙련도 높이기
            start = cur + 1
    if last_cur == 0:
        return 1
    return last_cur  # 최소 숙련도 반환