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

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

🔗 문제 링크

---

문제 설명 📄

퍼즐 조각 난이도를 조정하는 게임
diffs 리스트는 각 퍼즐 조각의 난이도를 나타냄.
times 리스트는 각 퍼즐 조각을 맞추는 데 걸리는 시간.
제한 시간 limit 내에서 최대한 난이도를 낮춘 상태에서 모든 퍼즐을 맞추려면 최소 난이도는 얼마인가?

---

문제 접근 방식 💡

• 누적 시간 계산
  • times 리스트를 사용하여 각 퍼즐 조각이 얼마나 걸리는지 누적.
• 최소 난이도 탐색
  • 이진 탐색을 사용하여 limit 내에서 가능한 최소 난이도(level)를 찾음.

---

Solution 💻

def solution(diffs, times, limit):
    faild = [times[0]]
    for i in range(1, len(diffs)):
        faild.append(times[i] + times[i - 1])
    
    def solveTime(level):
        cur_time = 0
        
        for i in range(len(diffs)):
            if diffs[i] > level:
                cur_time += (diffs[i] - level) * faild[i] + times[i]
            else:
                cur_time += times[i]
        
        return cur_time
    
    left, right = 1, max(diffs)
    
    while left < right:
        mid = (left + right) // 2
        if solveTime(mid) <= limit:
            right = mid
        else:
            left = mid + 1
    
    return left

시간 복잡도 분석 ⏲️

• 이진 탐색: O(log max(diffs))
• 시간 계산 (solveTime): O(n)
• 총 시간 복잡도: O(n log max(diffs))