[프로그래머스][PCCP 기출문제] 2번 - 퍼즐 게임 챌린지 (파이썬 풀이)

4년만에 돌아왔습니다~.~

2025년에는 공부하고 발전하는 한 해가 되길 바라며

2025년 첫 알고리즘 문제 풀어보았어요

 

확실히 오랜만에 푸는 알고리즘 문제라서

문제 이해하는거만 한참 걸렸네요 ^_ㅠ..

꾸준히 하면 조금 덜 바보가 되겠죠..?

---

퍼즐 게임 챌린지 문제입니다.

• 난이도: Lv2
• 풀이 언어: 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 함수를 완성해 주세요.

요약하자면,

• 현재 퍼즐의 난이도(diff)가 내 숙련도(level)보다 작거나 같으면 현재 퍼즐의 소요시간(time_cur) 만큼의 시간 사용
  • diff <= level: time_cur 사용
• 현재 퍼즐의 난이도(diff)가 내 숙련도(level)보다 크면 퍼즐을 '퍼즐 난이도 - 숙련도' 만큼 틀림
  • diff > level: diff-level 만큼
• 틀릴 때 마다 현재 퍼즐의 소요시간(time_cur)만큼의 시간을 사용,
  이전 퍼즐 소요시간(time_prev)만큼의 시간을 써서 이전 퍼즐도 풀어야 함!! 
  • 틀릴 때 마다 (time_cur + time_prev) * (diff - level) 의 시간을 사용
• diff-level 만큼 틀리고 나면 현재 퍼즐 소요시간(time_cur)만큼의 시간을 써서 퍼즐 최종 해결

 

• 구해야하는 결과: 전체 제한 시간 limit 내에 퍼즐을 모두 해결하기 위한 숙련도 level 의 최솟값
• 주어지는 변수
  • diffs: 퍼즐의 난이도를 순서대로 담은 1차원 정수 배열
  • times: 퍼즐의 소요 시간을 순서대로 담은 1차원 정수 배열
  • limit: 전체 제한 시간

 

내 풀이:

주어진 diffs (문제 난이도) 값 중 최대값 이하일 것이란거는 예측 가능합니다.

최대 diff 보다 숙련도가 높으면 모든 문제를 다 한번에 풀 수 있기 때문이죠

 

결론, 최대 diff 보다는 작지만 제한 시간 내에 문제를 풀 수 있는 최소 값을 찾아야 합니다!

 

그치만 1부터 max(diffs) 값 까지 모든 값을 순회하며 값을 찾을 수는 없습니다...성능이슈~

성능적 문제 해결을 위해 범위를 최대한 줄여가며 반복 탐색하게 해주는게 해결안입니다

-> 이진탐색 트리를 사용하기로 결정!

 

물론 저는 이진탐색트리를 바로 떠올리진 못했어요,. 키득..

반복문 다 돌리는거 오반데..싶어서 긴 고민을 해내서 생각했습니다..

 

일단 숙련도(level)에 따라 퍼즐 해결에 걸리는 전체 시간을 계산하는 로직을 먼저 만들었습니다

for i in range(1, len(diffs)):
    retry = max(0, diffs[i] - curLevel)
    solvedTime += (times[i] + times[i-1]) * retry + times[i]

 

 

현재 문제 난이도가 내 숙련도보다 큰 경우, 양수 값이 발생할 것이기 때문에

retry(문제 재풀이 횟수)를 구하는 것에 max 함수를 활용했습니다

def solution(diffs, times, limit):
    level = 1 # 숙련도
    maxLevel = max(diffs) # 최대 난이도
    answer = maxLevel
    
    # 이진탐색 활용
    while level <= maxLevel:
        curLevel = (level + maxLevel) // 2
        solvedTime = times[0] # diffs[0]은 항상 1이므로 첫 문제는 바로 해결 된다고 봄
        
        for i in range(1, len(diffs)):
            retry = max(0, diffs[i] - curLevel)
            solvedTime += (times[i] + times[i-1]) * retry + times[i]
        
        if solvedTime <= limit:
            answer = curLevel
            maxLevel = curLevel - 1 # while문이 정상적인 타이밍에 종료되도록 값 갱신
        else:
            level = curLevel + 1
    return answer

 

막상 다 풀고보니 간단했던 문제였습니다.. 풀고나니 잼있네용.

오늘의 알고리즘 풀이 끝~

 

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/340212

프로그래머스