[JS] Binary Search - 입국심사

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

프로그래머스

Question

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

 

---

solution

step 1.

제한사항을 보면 입국심사를 기다리는 사람, 각 심사관의 심사 시간의 최댓값들은 각각 10억 이하이다.

따라서 for문같은 반복문을 돌릴 때는 가장 범위가 적은 심사관 수로 돌리는 것이 가장 좋지만.. ㅎㅎㅎㅎ

어쨌든 이렇게 많은 숫자를 가진 제한사항이라면 선형시간을 쓰는 것보단 로그시간이 걸리는 풀이를 쓰는 것이 가장 좋다.

로그시간이 걸리는 것은 이진탐색!

이진탐색을 위해선 배열이 먼저 정렬이 되어야하지만 times는 10만 이하이기때문에 선형시간으로 정렬하는 것도 충분히 가능하다.

 

step 2.

이진탐색을 사용하지만 우리는 특정한 값을 찾는 것이 아니고, "최소 몇 분에 모든 심사가 끝나는가"이다.

이렇게 특정한 값을 찾는 게 아니라, 조건에 맞는 값을 찾아나가는 것을 [결정 문제]라고 부른다.

이러한 결정문제를 풀어나가는 것을 우린 이진탐색으로 풀지만 이러한 풀이를 [파라메트릭 서치 (Parametric Search)]라고도 부른다.

 

step 3.

정답은 최소 1분에서 n * 10억분 사이일 것이다.

그리고 면접관들이 몇 명을 처리하는가?를 알아내는 것이 중요하다.

처리 가능한 입국자가 n보다 작다면, 분을 올려야되고, 입국자가 n보다 크다면, 분을 내려야한다.

면접관이 시간대비 몇 명을 처리할 수 있는가 -> [전체 시간 / 심사 시간 = 심사관 당 처리 가능한 입국자 수]

 

 

1. 먼저 이진탐색을 쓰기위해 times를 오름차순으로 정렬해주고, left와 right를 정해준다.

심사하는데 걸리는 시간은 최소 1분이기때문에 left는 1로정한다.

심사하는데 가장 오래 걸리는 시간으로, right는 정렬된 시간의 가장 마지막 (가장 오래 걸리는 시간) * n으로 정해준다.

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

2. 이진탐색 루프를 돌려주자.

최소시간이 걸려야하므로 left가 right보다 작거나 같을 경우에만 루프를 돌려준다.

그 안에서 중간 값인 mid를 정해준다.

여기서 mid는 정답이 되는 입국 심사 전체 시간이다.

function solution(n, times) {
  const sortedTimes = times.sort((a, b) => a - b); // O(n log n)
  let left = 1;
  let right = sortedTimes[sortedTimes.length - 1] * n;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
  }
}

3. [전체 시간 / 심사 시간 = 심사관 당 처리 가능한 입국자 수] 이므로 이걸 각각의 심사관에게 적용시켜 모두 더해준 값은 n이 되어야한다.

해당 값의 합을 sum이라고 하고 더한 후 n과 비교를 해보자.

이런식으로 하다가 left가 right를 넘어서는 순간이 올 것이다. 이때 반환은 역전되기 직전에 더해지는 값을 return하면 된다.

이제 종료되기 전에 더해졌기때문에 left를 return 해주자.

function solution(n, times) {
  const sortedTimes = times.sort((a, b) => a - b); // O(n log n)
  let left = 1;
  let right = sortedTimes[sortedTimes.length - 1] * n;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const sum = times.reduce((a, time) => a + Math.floor(mid / time), 0);
    
    if (sum < n) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return left;
}