[프로그래머스/JS] 입국심사

[프로그래머스/JS] 입국 심사

1. 문제

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

2. 제한사항

입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
심사관은 1명 이상 100,000명 이하입니다..

3. 풀이

• 이분 탐색으로 풀었다.
• 몇 분까지 탐색할 지 기준으로 이진 탐색하였다.
• start = 1, end = 1000000000000000000라고 잡았다.
  • 입력 범위가 워낙 방대해서 최대한 큰 값을 잡았다.
• mid(몇 분까지 탐색할지)분동안 각 심사관이 몇 명을 심사할 수 있는지를 구해서 result에 저장한다.
  • 시간이 넘어가면 심사를 할 수 없기 때문에 몫만 구해서 더한다.
• 구한 값이 n(심사 받아야하는 사람) 보다 적으면 시간이 너무 부족한 것이기 때문에 시간을 늘린다.
  • start = mid + 1
• 구한 값이 n보다 크거나 같으면 시간이 충분하기 때문에 해당 값을 기록하고 시간을 줄인다.

4. 처음 코드와 달라진 점

• null

5. 코드

function solution(n, times) {
  var answer = 0;
  let start = 1;
  let end = 1000000000000000000;

  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    let result = 0;
    for (let t of times) {
      result += Math.floor(mid / t);
    }

    if (n <= result) {
      answer = mid;
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }
  return answer;
}