[프로그래머스 Level 3] 입국심사 - JavaScript

🔗 문제 링크

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

프로그래머스

✏️ 풀이

function solution(n, times) {
    let low = 1n;
    let high = 1_000_000_000n ** 2n;
    while (low <= high) {
        const mid = (low + high) / 2n;
        const people = times.reduce((acc, time) => acc + mid / BigInt(time), 0n);
        if (people < n) {
            low = mid + 1n;
        } else {
            high = mid - 1n;
        }
    }
    return low;
}

심사관 1명이 1명 심사하는데 최대 10억분이 소요되고, 입국심사를 기다리는 사람 또한 최대 10억명까지 입력으로 주어지므로, 사실상 최대 10^18분까지 소요될 수 있다. 이렇게 큰 숫자는 자바스크립트에서 BigInt를 사용해서 다뤄야 한다.

 

1분부터 10^18분까지 중에서 이분탐색을 통해 n명의 입국심사 대기자를 심사할 수 있는 최적의 시간을 찾아야 한다.

일단 먼저 X분일 때 최대 몇 명의 사람을 심사할 수 있는지 어떻게 알 수 있을까?

 

예를 들어, times가 [7, 10]일 때 30분 동안 최대 몇 명의 사람을 심사할 수 있을까? 심사관이 쉬지 않고 심사를 계속 했다고 가정하면 7분이 걸리는 심사관은 4명을 심사하고 1명을 심사중인 상태일 것이고, 10분이 걸리는 심사관은 3명을 딱 심사를 마쳤을 것이다. 그렇다면 30분 동안에 최대 7명을 심사할 수 있는 것이다. 즉, 각 심사관 별로 심사에 걸리는 시간으로 경과 시간을 나눠서 그 몫을 구하여 전부 더하면 X분일 때 심사 가능한 최대 인원의 수를 구할 수 있다.

 

1분부터 10^18분 사이에서 이분탐색을 통해 X분 동안 심사 가능한 최대 인원이 6이 되는 최소한의 시간을 찾아서 반환하였다.

 

 

function solution(n, times) {
    let low = 1;
    let high = Math.max(...times) * n;
    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        const people = times.reduce((acc, time) => acc + Math.floor(mid / time), 0);
        if (people < n) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return low;
}

이상하게도 이 문제는 BigInt를 사용하지 않아도 통과가 되는 것 같다. 아마 테스트케이스에 큰 수에 대한 케이스가 없어서 그런 것 같다.