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

🔥문제링크

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

프로그래머스

 

🔥풀이

제한사항을 보면서 바로 이진탐색으로 접근하라는 냄새를 맡을 수 있었다. 이진탐색으로 접근 안한다면 괴랄할만큼의 연산 횟수가 필요하고 그럼 분명히 시간초과 이슈가 생기기 때문이다. 다행히 해당 접근이 맞았고 해결!

function solution(diffs, times, limit) {
    
    let max = 100000, min = 1, mid = undefined
    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
    
}