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

문제 설명

 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

 

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

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

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

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

 

 

나의 풀이 

 처음에 왜 이 문제가 이진탐색 문제인지 이해가 안갔다. 그 상태에서 머리를 더 굴려봤자 답은 안나올 것이라 판단해서 바로 구글링을 했다. 항상 남의 코드 읽는 건 어렵다. 코드를 파헤쳐보니 이 문제는 이진탐색 문제가 맞다는 것을 느꼈다. 위의 예시를 들어보면서 풀이를 시작하도록 하겠다.

 

 

 이진탐색은 내가 찾으려는 값을 범위라는 것을 이용하여 탐색하는 것을 말한다. 범위에는 무조건 최솟값, 최댓값이 있어야 한다. 따라서 우리는 탐색을 하기전에 최솟값과 최댓값을 설정해줘야한다. 최솟값은 당연히 0이나 1로 대충 때리면 되고, 최댓값은 현재 상황을 고려해야한다. 무턱대고 Infinity 값을 주면 곤란하기 때문.

 

 

 times를 보자. 현재 times 배열에는 7, 10이라는 원소가 있다. 각 원소가 뜻하는 것은 입국 심사위원 A에게 심사를 받으면 7분이라는 소요시간이 걸리고, 입국 심사 위원 B에게 심사를 받으면 10분이 걸린다는 것이다. 그렇다면, 최대 소요시간(최댓값)은 6명 모두 심사위원 B에게 입국심사를 받는 경우다. 따라서 최댓값은 60이다.

 

 

 그렇다면, 최댓값인 60분을 제한시간으로 두어 심사위원 A,B에게 입국심사를 받는다고 가정할 때, 입국 심사를 받는 인원은 몇 명일까?

60/7 + 60/10 으로 총 14명이 된다. 14명은 n(=6)보다 크기 때문에, 우리는 최솟값(=0)과 최댓값(=60)을 더해서 2로 나눠야 한다.

 

 

 두 값을 더해 2로 나누면 30이 된다. 그럼 이제 30분을 제한시간으로 두면 총 몇명이 입국 심사를 받을 수 있는지 계산을 해야한다. 30/7 + 30/10으로 총 7명이 된다. 7명은 n(=6)보다 크기 때문에 최댓값은 30 - 1이 된다.  1을 빼는 이유는 최종 정답의 최솟값을 구하기 위해서다. 우리가 구해야 하는 정답이 의미하는 것은 최소 몇 분의 제한시간을 두어야 6명 모두 심사위원 A, B에게 입국심사를 받을 수 있느냐다. 위 예제에서 정답은 28, 29가 나온다. 둘 다 명 수를 산출하면 6 명이 나오기 때문이다.

 

 

 다시 돌아오면 최솟값은 0, 최댓값은 29다. 여기서 다시 중간 값을 계산하면 14가 된다. 14분 안에 입국 심사를 받을 수 있는 인원은 3 명이다. 3명은 n(=6)보다 작기 때문에 최솟값은 14 + 1으로 15가 된다. 이런식으로 최솟값이 최댓값보다 커질 대 까지 반복문을 돌리면 우리는 결과적으로 정답의 경우의 수 중에서 최솟값을 얻어낼 수 있다. 

 

 

 코드는 다음과 같다.

const solution = (n, times) => {
  times.sort((a,b) => a-b);
  let left = 0;
  let right = times[times.length-1]*n;
  let mid = Math.floor((left+right)/2);

  while(left <= right){
    const count = times.reduce((result, cur) => result + Math.floor(mid/cur), 0);

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

    mid = Math.floor((left+right)/2);
  }

  return left;
}