(javascript) 입국심사

코딩테스트 연습 - 입국심사 | 프로그래머스 스쿨

프로그래머스

 

이분 탐색을 사용하는 문제다.

처음에는 시뮬레이션으로 풀려고 했는데, 제한사항에 주어진 숫자가 너무 커서 안되겠다 싶었다.

 

핵심은 입국심사에 걸리는 총 시간 t가 특정 범위 안에 있다는 점이다. 범위를 정할 수 있고, 정렬되어있다면 이분 탐색을 적용할 수 있다.

 t의 범위는 최소 1이다. 모든 사람들이 1분만에 심사를 끝내는 경우이다.

 t의 범위의 최대는 가장 느리게 심사하는 심사관 * 입국자 수(n)이다. 이 심사관이 모든 입국자를 심사한다고 볼 수 있다.

 

 t에 대해서 이분탐색을 적용한다. t의 값을 범위 안에서 반씩 쪼개며 t시간동안 심사하는 사람의 수를 계산한다.

 만약 t시간동안 심사한 사람의 수가 n보다 적다면, 시간이 부족하다는 뜻이므로 t를 오른쪽 범위로 이동한다.

 만약 t시간동안 심사한 사람의 수가 n보다 크다면, 시간이 충분하다는 뜻이므로 t를 왼쪽 범위로 이동한다.

 

 최종적으로 left와 right값이 교차하게 되면 t의 최소값을 찾게 된다.

 

코드

function solution(n, times) {
    n = BigInt(n);
    var answer = 0n;
    var left = 1n;
    var right = n * BigInt(Math.max(...times));

    while (left <= right) {
        var mid = (left + right) / 2n;
        var sum = 0n;
        for (var i = 0; i < times.length; i++) {
            sum += mid / BigInt(times[i]);
            if (sum >= n) break;
        }
        if (sum < n) {
            left = mid + 1n;
        } else if (sum >= n) {
            answer = mid;
            right = mid - 1n;
        }
    }

    return Number(answer);
}

결과

문제해결

풀이 과정에서 몇가지 문제가 발생했다.

 

1. 시간초과 문제

 처음 코드를 작성했을 때, t시간동안 심사한 사람의 수를 구하는 함수로 Array.reduce를 사용했다. reduce는 배열의 각 요소를 순회하며 콜백함수를 실행해 결과를 누적시키는 함수이다. 

var sum = times.reduce((acc, cur) => {
    return acc + Math.floor(mid / cur);
}, 0);

 그러나 우리는 t시간동안 심사한 사람의 수를 끝까지 계산할 필요가 없다. 만약 결과가 n보다 커지면 그 순간 중단하고 다음으로 넘어가도 된다.

 따라서 reduce 함수를 사용하는 대신 단순 반복문으로 수정하고, 대신 sum > n이 되면 반복문을 탈출하도록 했다.

var sum = 0n;
for (var i = 0; i < times.length; i++) {
    sum += mid / BigInt(times[i]);
    if (sum >= n) break;
}

 

2. 또 시간초과 문제

 그럼에도 여전히 시간초과가 발생했다. JavaScript 내부적으로 큰 숫자를 다룰 때 발생하는 문제라고 생각한다.

 JavaScript의 Number는 64비트 부동소수로, 53비트가 넘는 정수는 안전하지 않다. 주어진 제한사항에서 right값을 계산할 때 이 범위를 벗어나 결과에 오차가 발생할 수 있다.

 따라서 큰 수를 다루는 BigInt를 사용해야한다.

BigInt - JavaScript | MDN

BigInt - JavaScript | MDN