[프로그래머스][이분 탐색] 퍼즐 게임 챌린지

 

     

목차

 

 

문제

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

프로그래머스

 

 

문제 구현 시 주의점

이분탐색으로 하면 쉽게 풀리나 숫자의 범위가 매우 크기 때문에 js로 풀 경우 테스트를 통과하지 못하니 주의하자

bigint를 써서 풀어야 한다.

 

 

코드 구현

let answer = 0n;

function cacul(diffs, times, level, limit) {
    let process = 0n;
    for (let idx = 0; idx < diffs.length; idx++) {
        const diff = BigInt(diffs[idx]);
        const time = BigInt(times[idx]);
        const levelBig = BigInt(level);

        if (levelBig < diff) {
            if (idx === 0) {
                process += (diff - levelBig + 1n) * time;
            } else {
                const prevTime = BigInt(times[idx - 1]);
                process += (diff - levelBig) * (prevTime + time) + time;
            }
        } else {
            process += time;
        }
        if(limit < process)return Math.Infinity;
    }
    return process;
}

function binarySearch(diffs, times, limit) {
    let start = 1n;
    let end = 100001n;
    let final = 100001n;
    const limitBig = BigInt(limit);

    while (start <= end) {
        let mid = (start + end) / 2n;
        let ans = cacul(diffs, times, mid, limitBig);

        if (ans <= limitBig) {
            final = mid < final ? mid : final;
            end = mid - 1n;
        } else {
            start = mid + 1n;
        }
    }

    answer = final;
}

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