[Javascript/PGS] Lv.2 : 퍼즐 게임 챌린지 (PCCP 기출문제 2번)

 

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

프로그래머스

---

프로그래머스 레벨2.

정답률 42%인 PCCP 기출이다

다음 달에 PCCP 도전해볼까 해서 기출을 풀어보았다!

 

처음에 limit 범위가 너무 크길래, 이거 설마 이분탐색...?! 이러면서 풀었는데

역시나 이진 탐색 유형의 문제가 맞았다.

자주 푸니까 슬슬 문제 유형이 눈에 보이는듯 😇

 

while 종료 조건, left / right 갱신, answer 갱신 등 신경써야할 부분이 많았다!!!

 

특히 난이도, 소요 시간은 모두 양의 정수며, 숙련도도 양의 정수여야 합니다.라는 조건이 있으므로,

최솟값이 0이 아닌 1부터 시작이어야 함

 

나의 풀이

function solution(diffs, times, limit) {
    let answer = 100001;
    let max = 0; let maxIdx = 0;
    let len = diffs.length;
    // 최댓값과 인덱스 찾기
    diffs.forEach((d, i)=>{
        if(max<d) {
            maxIdx = i;
            max = d;
        }
    })
    // 인덱스 이진탐색
    let left = 1;
    let right = max;
    
    while(left <= right){
        let level = Math.floor((left+right)/2);
        let time = 0;
        // console.log(left, level, right);
        for(let i=0; i<len; ++i){
            if(diffs[i]<=level){
                time += times[i];
            }
            else{
                let wrong = diffs[i]-level;
                if(i==0) {
                    time += wrong * times[i] + times[i];
                }
                else time += wrong * (times[i]+times[i-1]) + times[i];
            }
        }
        // 제한시간보다 더 오래걸리면 -> 레벨 높이기
        if(time > limit){
            left = level+1;
        }
        else {
            answer = Math.min(answer, level);
            right = level-1;
        }
    }
    return answer;
}