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

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

프로그래머스

 

제한사항
1 ≤ diffs의 길이 = times의 길이 = n ≤ 300,000
diffs[i]는 i번째 퍼즐의 난이도, times[i]는 i번째 퍼즐의 소요 시간입니다.
diffs[0] = 1
1 ≤ diffs[i] ≤ 100,000
1 ≤ times[i] ≤ 10,000
1 ≤ limit ≤ 1015
제한 시간 내에 퍼즐을 모두 해결할 수 있는 경우만 입력으로 주어집니다.

 

 

문제를 보자마자 감이 오지 않았고 완전 탐색처럼 진행했다가 시간만 날렸다. 그러다 중간점을 찾으면 되는 문제라는 것을 불현듯 깨닫고 이진 탐색이라는 키워드로 접근했지만, 하도 오래된 알고리즘 공부로 구현 로직이 막혔다.

 

아래는 이해가 제일 잘된 분의 코드이다.

 

function solution(diffs, times, limit) {
    let max = 100000, min = 1, mid = 0
    let answer = max
    while(min<=max){
        mid = Math.floor((max+min)/2)
        let spendTime = 0, over = false
        for(let i=0; i<diffs.length; ++i){
            
            if(mid-diffs[i]<0){
                spendTime = spendTime + (diffs[i]-mid)*(times[i]+times[i-1]) + times[i] 
            }else{ 
                spendTime+= times[i]
            }
            
            if(limit<spendTime){
                over = true
                break;
            }
        }
        
        if(over){
           min = mid + 1
        }else{
           answer = mid 
           max = mid -1 
        }
        
    }
    return answer
    
}

 

막연히 어렵게 느꼈지만 결국 이진탐색 알고리즘과 초과시간에 대한 공식만 잘 세우면 풀 수 있는 문제였다. 역시 본질은 쉬우나 그 파악이 어려운듯 하다.

 

동작 과정

1. 초기 설정

let max = 100000, min = 1, mid = 0 let answer = max

• min: 난이도의 최솟값(1).
• max: 난이도의 최댓값(100,000).
• answer: 조건을 만족하는 최적의 난이도 기준값을 저장.

2. 이진 탐색 루프

while (min <= max) {
    mid = Math.floor((max + min) / 2)
    let spendTime = 0, over = false
    for (let i = 0; i < diffs.length; ++i) {
        if (mid - diffs[i] < 0) {
            spendTime = spendTime + (diffs[i] - mid) * (times[i] + times[i - 1]) + times[i]
        } else { 
            spendTime += times[i]
        }
        if (limit < spendTime) {
            over = true
            break
        }
    }
    if (over) {
        min = mid + 1
    } else {
        answer = mid
        max = mid - 1
    }
}

1. mid 계산
   • 현재 이진 탐색의 중앙값을 기준으로 난이도(mid)를 계산.
2. 소요 시간 계산 
   • 각 단계(diffs[i])에 대해 mid보다 난이도가 높으면 추가 시간이 발생:
     spendTime = spendTime + (diffs[i] - mid) * (times[i] + times[i - 1]) + times[i]
     
     
      
     여기서:
     • (diffs[i] - mid): 난이도 초과량.
     • (times[i] + times[i - 1]): 해당 초과량의 시간 가중치.
     • times[i]: 현재 단계의 기본 소요 시간. 
       • 난이도가 기준 이하일 경우 기본 소요 시간만 추가:
         spendTime += times[i]
3. 시간 초과 체크
   • spendTime이 limit보다 크면, mid를 늘려야 하므로 min을 증가:
     min = mid + 1
     
     
   • spendTime이 limit 이하라면, 조건을 만족하므로 answer를 갱신하고, 난이도 기준을 낮추기 위해 max를 감소:
     answer = mid
     max = mid - 1

---

 

사용된 알고리즘: 이진 탐색 (Binary Search)

이 코드는 이진 탐색을 사용하여 난이도 기준값(mid)를 점진적으로 좁혀갑니다.

왜 이진 탐색을 사용했는가?

1. 난이도 기준값(mid)의 범위가 정렬된 형태 (1부터 100,000까지).
2. 최적의 값(최소 난이도 기준)을 찾아야 하므로, 이진 탐색으로 탐색 공간을 절반씩 줄이는 것이 효율적.

시간 복잡도

• 이진 탐색: 난이도의 범위를 절반씩 나누므로 O(log⁡N).
• diffs 배열 순회: 각 mid에 대해 O(M) (M은 diffs.length).
• 전체 시간 복잡도: O(M⋅log⁡N).

---

결론

이 코드는 이진 탐색을 사용하여 난이도 기준값(mid)를 찾고, 각 난이도에 따른 소요 시간을 계산하여 최적의 기준값을 도출합니다.

 

만약 반복문 대신 완전 탐색을 사용했다면, O(M⋅N)의 시간 복잡도로 인해 비효율적이고, 제한 시간이 초과될 가능성이 높습니다.

 

이진 탐색을 사용하여 이를 효율적으로 해결한 점이 주요 장점입니다.