[알고리즘] 입국 심사

들어가며 

이진 탐색 - JavaScript를 먼저 공부한 다음 푼 문제입니다. 

바로 풀리지 않거나 설명이 필요하다면 참고하는 것을 추천드립니다. 

문제 설명

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

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

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

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

제한사항

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

입출력 예

n	times	return
6	[7, 10]	28

입출력 예 설명

가장 첫 두 사람은 바로 심사를 받으러 갑니다.

7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.

10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.

14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.

20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

나의 풀이

const times = [7, 10];
const n = 6;

// 1, 2, 3, 4, 5, 6
// 7 :  1, 3, 5, 6
// 10 : 2, 4,

function findMinArray(arr, times) {
  let value = Infinity;
  let index = 0;

  for (let i = 0; i < arr.length; i++) {
    if (value > arr[i] + times[i]) {
      value = arr[i] + times[i];
      index = i;
    }
  }

  return index;
}

function solution(n, times) {
  var answer = 0;
  const delay = Array(times.length).fill(0);

  while (n !== 0) {
    const minDelay = findMinArray(delay, times);
    delay[minDelay] += times[minDelay];

    n--;
  }

  for (const item of delay) {
    answer = Math.max(answer, item);
  }

  return answer;
}

console.log(solution(n, times));

배열을 사용해서 대기 시간을 더 하고 마지막에 Math.max를 사용해 최종 시간을 나타냈다. 

심사를 기다리는 사람의  값이 커질수록 걸리는 시간이 길어져서 결국 시간 초과가 발생했다. 

 

const times = [7, 10];
const n = 6;

// 1, 2, 3, 4, 5, 6
// 7 :  1, 3, 5, 6
// 10 : 2, 4,

function solution(n, times) {
  const sortTimes = times.sort((a, b) => a - b);
  let left = 1;
  let right = sortTimes[sortTimes.length - 1] * n;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    const sum = sortTimes.reduce(
      (acc, data) => acc + Math.floor(mid / data),
      0
    );

    if (sum < n) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return left;
}

console.log(solution(n, times));

이진 탐색의 방법을 사용했는데, 

최소 시간 ( left )와 최대 시간 ( right = 가장 시간이 오래걸리는 심사관이 전체를 처리한 시간)

을 활용 하였다. 

 

mid는 중간 처리 시간으로 " mid 시간 안에 심사관들은 몇 명을 처리할 수 있는지? "를 활용해서

만약 mid 시간 안에 n 보다 많은 인원을 처리한 경우 시간을 줄일 수 있다고 판단해서 right = mid - 1 

반대로 mid 시간 안에 n 보다 적은 인원을 처리하면 시간이 더 필요해서 left = mid + 1을 사용해서 

문제를 풀었다.