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

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

프로그래머스

간단한 이분탐색 문제지만 한가지 고려해야 할 부분이 있습니다.

문제 지문에 숙련도가 양의 정수라는 부분이 반례가 될 수 있는데 저는 오래도록 눈치채지 못했습니다.

limit 시간이 충분히 긴 경우 숙련도가 0인 경우에도 시간 안에 통과가 가능해보이지만 양의 정수만 가능하다는 것을 고려해야합니다.

 

이 글을 보는 분께 도움이 되셨다면 좋겠습니다. 행복 코딩테스트되세요 :)

function solution(diffs, times, limit) {
    return binarySearch(diffs, times, limit);
}

const binarySearch = (diffs, times, limit) => {
    let start = 0;
    let end = 100_000;
    
    while (start < end) {
        const mid = Math.trunc((start + end) / 2);
        
        if (canAllPassInLimit(diffs, times, limit, mid)) {
            end = mid;
        } else {
            start = mid + 1;
        }
    }
    
    return start || 1;
}

const canAllPassInLimit = (diffs, times, limit, level) => {
    let currentTime = 0;
    
    for (let i = 0; i < diffs.length; i++) {
        const diff = diffs[i];
        const time = times[i];
        
        if (diff <= level) {
            currentTime += time;
        } else {
            const repeat = diff - level;
            const previousTime = i === 0 ? 0 : times[i - 1];
            currentTime += ((previousTime + time) * repeat) + time;
        }
        
        if (currentTime > limit) {
            return false;
        }
    }
    
    return true;
}