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

< 처음 풀이>

function solution(diffs, times, limit) {
    var answer = 0;
    let level = 1;
    
    while(true){
        let solved_time=0;
        for(let i=0;i<diffs.length;i++){
            if(i ==0)
                solved_time = times[i];
            else {
                if(diffs[i]<=level){
                    solved_time+=times[i];
                }
                else {
                    solved_time+=(diffs[i]-level)*(times[i]+times[i-1])+times[i];
                }
            }
        }
        if(solved_time<=limit){
            answer=level;
            return answer;
        }
        level++;
    }
}

➡️ 처음에는 위와 같이 풀이를 진행했는데, level 을 1부터 계속 반복문을 돌다 보니, 시간이 초과됐다. 

 

< 시간 초과 해결>

function solution(diffs, times, limit) {
    let left =1;
    // max 는 이전 반환값, curr 은 현재 처리할 요소
    let right = diffs.reduce((max, curr) => Math.max(max, curr), 0); 
    
    while(left <= right) {
        const mid = Math.floor((left+right)/2); // 현재 숙련도 
        let totalTime = 0;
        let isValid = true;
        
        for(let i=0;i<diffs.length;i++){
            if(i == 0)
                totalTime = times[i];
            else {
                if(diffs[i]<=mid){
                    totalTime+=times[i];
                }
                else {
                    totalTime+=(diffs[i]-mid)*(times[i]+times[i-1])+times[i];
                }
            }
            if(totalTime > limit) { // 중간에 소요시간 초과이면 
                isValid = false; // 유효하지 않음
                break; // 반복문 종료 
            }
        }
        
        if(isValid) // 소요시간을 초과하지 않았다면 
            right = mid - 1; // 값을 더 작게 하여 숙련도의 최솟값 찾기
        else // 다 돌고 난 후 소요시간 초과이면 
            left = mid + 1; // 값을 더 크게 하여 올바른 범위 내의 숙련도 찾기 
    }
    
    return left;
}

➡️ 시간 초과 문제를 해결하기 위해서는 이진 탐색을 통해 문제를 해결해야 한다.

 

✏️ 풀이 방법

1. left 는 1로, right 는 diffs 배열의 최대값으로 설정한다. 

 

* right 를 diffs 배열의 최대값으로 설정하는 이유

=> 숙련도가 퍼즐의 최대 난이도보다 높아지더라도 추가적인 시간 단축이 없다. 예를 들어, 최대 난이도가 5이고 숙련도가 5,6,7,8 일 때 각각의 경우에 퍼즐을 푸는 데 걸리는 시간은 똑같다. 이 상황에서 최소 숙련도는 5이다. 최대 난이도보다 숙련도의 최솟값이 높아질 수 없다. 

 

2. left 가 right 보다 작거나 같을동안 반복문을 돈다. 

 

: mid 값을 현재 숙련도로 설정하여 해당 숙련도로 모든 퍼즐을 풀 수 있는지 확인

: 첫 번째 퍼즐 => 항상 times[i] 시간만 소요

  이후 퍼즐 => 난이도와 숙련도를 비교하며 시간 계산

: 소요 시간이 초과 되지 않으면 => 숙련도를 낮춰도(숫자가 작아져도) 되므로 right 의 값을 1 감소

  소요 시간이 초과되면 => 숙련도를 높여야(숫자가 커져야) 하므로 left의 값을 1 증가

  

3. 이진 탐색을 반복한 후의 left 값(숙련도의 최솟값)을 반환한다. 

 

✍🏻 느낀점

 

처음에 문제를 level 을 1부터 계속 증가시키는 방법으로 문제를 풀면서도, 시간 초과날 것 같은데? 생각했는데 역시나 시간초과가 났다..! ㅎㅎ 이진 탐색을 알고는 있었지만, 그동안 잘 쓰지 않아서 아예 잊고 있었는데 이번 문제를 통해서 상기시킬 수 있어서 좋았다. 근데 풀면서 왜 답이 mid 가 아니라 left 가 되는지가 궁금했는데 찾아보니, 탐색 과정에서 조건을 만족하는 경우에 left 는 mid+1 로, 조건을 만족하지 않는 경우에 right 는 mid-1 로 이동하면서 left 가 자연스럽게 조건을 만족하는 최솟값에 위치하게 되기 때문이라고 한다. 이거를 잘 기억해두고, 다음에 이진 탐색을 활용할 수 있는 문제가 있다면 잘 써먹어야겠다.☺️