[Programmers][Python] Lv.2 퍼즐 게임 챌린지

Overview

• 체감 난이도: ★★☆☆☆
• 문제 레벨: Lv.2_PCCP 기출문제
• 풀이 상태: 답안참고 / 스스로 해결
• 추후: 다시 풀어보기 / 간단 복습 / 완벽 이해 

---

[문제]

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

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

프로그래머스

 

 

[코드]

문제에서 구현하라는대로 구현하면 시간초과가 발생한다. 

 

(시간초과 코드)

def solution(diffs, times, limit):
    level = 1  # 숙련도 / limit 초과할 때마다 1씩 증가

    while True:
        total_time = 0  # 반복문 돌 때마다 리셋

        # diffs[0] = 1
        for i in range(len(diffs)):
            # 퍼즐 난이도 > 숙련도
            if diffs[i] > level:
                total_time += (diffs[i]-level) * (times[i]+times[i-1]) + times[i]
            # 퍼즐 난이도 <= 숙련도
            else:
                total_time += times[i]

        # exit 조건 - 퍼즐 다 푸는 시간이 limit 이하일 때
        if total_time <= limit:
            return level
        else:
            level += 1

 

 

<시간 초과 해결 방법>

→ 이분탐색/이진탐색으로 탐색 범위를 절반씩 좁혀 나간다. 

 

* 이진탐색이란?

2024.07.17 - [Algorithms/Code Tree] - [Code Tree] Binary Search 이진탐색

[Code Tree] Binary Search 이진탐색

 

<풀이 방법> 

첫번째 퍼즐 난이도는 1로 고정이다.

그리고 퍼즐 난이도 중에 제일 높은 난이도와 숙련도가 같을 경우,  퍼즐을 해결하는 데 최소의 시간이 나올 것이다. 

 

1. left를 최소 난이도인 1, right를 최대 난이도인 max(diffs)로 숙련도 범위를 설정해준다. (이진탐색 할 범위)

2. mid = (left + right) // 2 -> 탐색 시작할 중간 부분 설정

3. 퍼즐 난이도 > mid(현재 숙련도) 일 경우, (현재 난이도 - 숙련도) * (현재 난이도 + 이전 난이도) + 현재 난이도 (조건)

4. 아닌 경우, 현재 난이도만 더해준다. (조건)

5. total_time이 limit 이하일 경우, 가능한 더 낮은 숙련도를 찾는다. → right = mid

6. 초과할 경우, 숙련도를 높인다. → left = mid + 1

 

* exit 조건

- left와 right가 같아지는 시점에, 최적의 level을 나타내며 더 이상 탐색할 필요가 없으므로 while 루프를 빠져나온다. 

 

(정답 코드)

def solution(diffs, times, limit):
    left, right = 1, max(diffs)  # 숙련도의 범위를 1에서 최대 난이도 값까지 설정

    while left < right:
        mid = (left + right) // 2
        total_time = 0

        for i in range(len(diffs)):
            # 퍼즐 난이도 > mid (현재 숙련도)
            if diffs[i] > mid:
                total_time += (diffs[i] - mid) * (times[i] + times[i-1]) + times[i]
            else:
                total_time += times[i]

        # 퍼즐 다 푸는 시간이 limit 이하일 때
        if total_time <= limit:
            right = mid  # 가능한 더 낮은 level 찾기
        else:
            left = mid + 1  # 숙련도 부족, level을 높임

    return left  # 최소한의 level