[프로그래머스/Programmers] PccP 기출문제 2번_퍼즐 게임 챌린지 (JavaScript)

윶·2024년 11월 11일

알고리즘 뿌수기

목록 보기

3/4

🌱 문제

[프로그래머스/Programmers] PccP 기출 2번_퍼즐 게임 챌린지
내 전용 알고리즘 슨상님이 문제 추천을 해줬닷..! 자소서 쓰기도 이제 지치고 낡아버려서 알고리즘이 재미있게 느껴진다 ㅋ.ㅋ
어쨌든 바로 스따또

☘️ 풀이

킁킁 이진 탐색의 냄새가 난다..!!

diffs의 첫 번째 퍼즐이 level보다 클 경우 이전 퍼즐 시간을 더해야 하는데 이전 퍼즐이 없으므로.. times의 첫 번째 요소로 0초를 넣어준다.
level의 범위를 min인 1부터 diffs의 max 값까지로 정한다. (Math.max(...diffs)를 썼더니 마지막 테케 몇 개에서 런타임 에러가 났다 이런 ~! 그래서 조건에 주어진대로 max 값에 100000을 넣었다.)
level 범위의 중간값(mid)을 지정하여 이진 탐색을 한다.
3-1. diff <= level 이면 time_cur 만큼 시간 추가
3-2. diff > level 이면 (diff - level) * (time_cur + time_prev) + time_cur 만큼 시간 추가
총 시간에 따라 level 범위의 min과 max 값을 수정한다.
4-1. 총 시간 > limit인 경우, level이 더 높아져야 총 시간이 줄어든다. 👉 level의 min 값을 현재 level(mid) + 1로 수정한다.
4-2. 총 시간 <= limit인 경우, level이 더 낮아질 수 있다. 👉 level의 max 값을 현재 level(mid) - 1로 수정한다.
level 범위의 min 값이 max 값 이하일 동안 2 ~ 3 의 과정을 반복하고 탐색을 끝낸다!

function solution(diffs, times, limit) {
    times.unshift(0);  // 첫 번째 diff > lev 면 앞 퍼즐 시간 0초 추가
    
    let min_lv = 1;
    let max_lv = 100000;

    while (min_lv <= max_lv) {
        let level = Math.floor((min_lv + max_lv) / 2);
        let solve_time = 0;
        
        // 현재 level로 퍼즐 풀 때 걸리는 시간 계산
        for (let i = 0; i < diffs.length; i++) {
            if (diffs[i] > level) {
                solve_time += ((diffs[i] - level) * (times[i] + times[i + 1]) + times[i + 1]);  // times[i + 1]이 time_cur, times[i]가 time_prev
            } else {
                solve_time += times[i + 1]
            } 
        }
        
        if (solve_time > limit) min_lv = level + 1;
        else max_lv = level - 1;
        
        solve_time = 0;
    }
    return min_lv;
}