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

문제

당신은 순서대로 n개의 퍼즐을 제한 시간 내에 풀어야 하는 퍼즐 게임을 하고 있습니다. 각 퍼즐은 난이도와 소요 시간이 정해져 있습니다. 당신의 숙련도에 따라 퍼즐을 풀 때 틀리는 횟수가 바뀌게 됩니다. 현재 퍼즐의 난이도를 diff, 현재 퍼즐의 소요 시간을 time_cur, 이전 퍼즐의 소요 시간을 time_prev, 당신의 숙련도를 level이라 하면, 게임은 다음과 같이 진행됩니다.

• diff ≤ level이면 퍼즐을 틀리지 않고 time_cur만큼의 시간을 사용하여 해결합니다.
• diff > level이면, 퍼즐을 총 diff - level번 틀립니다. 퍼즐을 틀릴 때마다, time_cur만큼의 시간을 사용하며, 추가로 time_prev만큼의 시간을 사용해 이전 퍼즐을 다시 풀고 와야 합니다. 이전 퍼즐을 다시 풀 때는 이전 퍼즐의 난이도에 상관없이 틀리지 않습니다. diff - level번 틀린 이후에 다시 퍼즐을 풀면 time_cur만큼의 시간을 사용하여 퍼즐을 해결합니다.

예를 들어 diff = 3, time_cur = 2, time_prev = 4인 경우, level에 따라 퍼즐을 푸는데 걸리는 시간은 다음과 같습니다.

• level = 1이면, 퍼즐을 3 - 1 = 2번 틀립니다. 한 번 틀릴 때마다 2 + 4 = 6의 시간을 사용하고, 다시 퍼즐을 푸는 데 2의 시간을 사용하므로 총 6 × 2 + 2 = 14의 시간을 사용하게 됩니다.
• level = 2이면, 퍼즐을 3 - 2 = 1번 틀리므로, 6 + 2 = 8의 시간을 사용하게 됩니다.
• level ≥ 3이면 퍼즐을 틀리지 않으며, 2의 시간을 사용하게 됩니다.

퍼즐 게임에는 전체 제한 시간 limit가 정해져 있습니다. 제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 구하려고 합니다. 난이도, 소요 시간은 모두 양의 정수며, 숙련도도 양의 정수여야 합니다.

퍼즐의 난이도를 순서대로 담은 1차원 정수 배열 diffs, 퍼즐의 소요 시간을 순서대로 담은 1차원 정수 배열 times, 전체 제한 시간 limit이 매개변수로 주어집니다. 제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 정수로 return 하도록 solution 함수를 완성해 주세요.

---

규칙

1. 난이도와 숙련도 비교:

• 난이도(diff)가 숙련도(level)보다 낮거나 같은 경우: 퍼즐은 바로 풀립니다. 풀이에는 현재 퍼즐의 소요 시간(time_cur)만큼 시간이 듭니다.
• 난이도(diff)가 숙련도(level)보다 높은 경우:
  (diff - level)번 만큼 퍼즐을 틀립니다. 퍼즐을 틀릴 때마다 현재 퍼즐의 소요 시간(time_cur)과 이전 퍼즐의 소요 시간(time_prev)을 사용하여 이전 퍼즐을 다시 풀고 돌아와야 합니다.
  퍼즐을 모두 틀린 후, 다시 현재 퍼즐을 풀 때는 time_cur만큼의 시간을 추가로 사용합니다.

1. 시간 계산 예시:

diff = 3, time_cur = 2, time_prev = 4, level = 1:
2번 틀림 → 각 틀림에 6초 사용 (2초 퍼즐 + 4초 이전 퍼즐)
최종 풀이에 2초 추가 → 총 14초 (6초 * 2 + 2초)
level = 2:
1번 틀림 → 6초 사용 후 마지막에 2초 추가 → 총 8초
level ≥ 3:
바로 풀이 → 2초
문제 해결

---

포인트

이 문제를 효과적으로 해결하기 위해 이진 탐색을 활용하는 전략이 중요합니다. 주요 고려사항은 다음과 같습니다.

1. 이진 탐색 적용 : 이 문제에서는 제한 시간 내에 모든 퍼즐을 해결할 수 있는 최소 숙련도 수준을 찾기 위해 이진 탐색을 사용합니다. 이진 탐색을 통해 숙련도의 범위를 좁혀 나가면서, 각 숙련도 수준에서 모든 퍼즐을 풀 수 있는지 여부를 검증합니다.

2. 숙련도 범위 설정: 숙련도의 시작 범위를 퍼즐 난이도의 최소값으로, 끝 범위를 최대값으로 설정합니다. 이렇게 설정하는 이유는 난이도가 최소값 이하일 경우 모든 퍼즐을 쉽게 해결할 수 있고, 최대값 이상일 경우 가장 어려운 퍼즐도 쉽게 해결할 수 있기 때문입니다.

3. 시간 계산 검증: 각 숙련도 수준에서 모든 퍼즐을 해결하는 데 필요한 총 시간을 계산하고, 이 시간이 주어진 limit을 초과하는지 확인합니다. 이 계산은 각 퍼즐의 난이도와 주어진 숙련도를 비교하여 이루어지며, 숙련도가 낮을수록 더 많은 시간이 소요됩니다.

4. 효율적인 시뮬레이션: 주어진 숙련도에 대해 각 퍼즐을 순차적으로 해결하면서 필요한 총 시간을 누적하는 방식으로 시뮬레이션을 수행합니다. 만약 누적된 시간이 limit을 초과하면 해당 숙련도는 실패로 간주하고, 숙련도 범위를 조정합니다.

---

내 답안

def binary_search(diffs, times, limit, level):
    # 초기 시간 소모 계산 (모든 퍼즐의 기본 소요 시간 합)
    spend = sum(times)
    pre = 0  # 이전 퍼즐의 소요 시간 초기화

    # 모든 퍼즐에 대해 순회
    for i in range(len(diffs)):
        diff = diffs[i]  # 현재 퍼즐의 난이도
        time = times[i]  # 현재 퍼즐의 소요 시간
        if diff > level:  # 난이도가 현재 레벨보다 높은 경우
            # 이전 퍼즐의 소요 시간과 현재 퍼즐의 소요 시간을 곱한 후 추가
            spend += (pre+time)*(diff-level)
        if spend > limit:  # 총 소요 시간이 제한 시간을 초과하는 경우
            return False  # 이 레벨로는 모든 퍼즐을 풀 수 없음
        pre = time  # 현재 퍼즐의 소요 시간을 이전 소요 시간으로 업데이트
    return True  # 제한 시간 내에 모든 퍼즐을 해결할 수 있는 경우

def solution(diffs, times, limit):
    answer = 0  # 최소 숙련도를 저장할 변수

    # 숙련도 범위 설정
    left = min(diffs)  # 가능한 최소 숙련도
    right = max(diffs)  # 가능한 최대 숙련도

    # 이진 탐색을 통해 최소 숙련도 찾기
    while left <= right:
        level = (left+right)//2  # 중간값을 현재 숙련도로 설정
        # 현재 숙련도로 모든 퍼즐을 제한 시간 내에 해결 가능한지 확인
        if binary_search(diffs, times, limit, level):
            answer = level  # 가능한 경우, 답을 업데이트
            right = level-1  # 더 낮은 숙련도에서도 가능한지 탐색
        else:
            left = level + 1  # 불가능한 경우, 숙련도 범위를 높여서 다시 탐색

    return answer  # 최소 숙련도 반환

---

결론 및 느낀점

이 문제를 해결하면서 효율적인 알고리즘 설계의 중요성을 다시 한번 깨달았습니다. 특히, 제한된 시간 안에 최적의 해결책을 찾기 위한 이진 탐색의 적용은 매우 중요했습니다. 이 문제에서 이진 탐색을 사용함으로써, 가능한 숙련도 범위를 효과적으로 좁혀나가며, 각 시도마다 모든 퍼즐을 제한 시간 내에 해결할 수 있는지를 판단할 수 있었습니다.

핵심 학습 포인트:

1. 이진 탐색의 적용:
   이진 탐색은 숙련도 수준을 결정하기 위해 매우 효과적이었습니다. 이 방법을 통해, 주어진 범위 내에서 가능한 숙련도 수준을 빠르게 좁혀나갈 수 있었으며, 각 단계에서 모든 퍼즐을 제한 시간 내에 해결할 수 있는지 여부를 효율적으로 검증할 수 있었습니다.

2. 시간 관리:
   각 퍼즐의 소요 시간과 이전 퍼즐로 돌아가는 시간을 고려하여 시간을 계산하는 방식은 문제 해결에 있어 핵심적이었습니다. 숙련도가 낮을수록 퍼즐을 푸는데 더 많은 시간이 소요되는 점을 감안하여, 최소한의 시간을 보장하는 숙련도 수준을 찾는 것이 중요했습니다.

3. 알고리즘 효율성:
   효율적인 알고리즘 설계는 이와 같은 최적화 문제에서 매우 중요합니다. 복잡한 조건과 다양한 변수를 고려하면서도, 실행 시간과 자원 사용을 최적화하는 방법을 고민해야 했습니다.

이러한 경험을 통해, 알고리즘 문제 해결 능력을 향상시키고, 실제 소프트웨어 개발 상황에서의 성능 최적화 기술을 더욱 발전시킬 수 있는 기회가 되었습니다. 또한, 문제의 조건을 정확히 분석하고 이를 기반으로 효과적인 해결 방안을 설계하는 방법을 배울 수 있었습니다.