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

문제 : 프로그래머스 - 입국심사

카테고리 : 이분탐색

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

---

✏️내 풀이

이 문제를 보고,

" 모든 입국자가 각 심사관에게 심사를 받았을 때, 모든 입국자의 심사가 끝났을 때 걸리는 시간이 최소가 되도록, 각 입국자들 심사관에게 배정해야 한다 " 라고 생각했다.

그래서, 각 심사관마다 입국자를 어떻게 배정해야 할지를 고민했다.

예를 들어, 입국자가 5명이고, 각 심사관들이 3명이고, 각 심사관이 한 명을 심사하는데 걸리는 시간이 [2, 3, 7] 이라면

심사관1	심사관2	심사관3
5	0	0
4	1	0
3	1	1

이렇게 각 case를 나눠서, case마다 각 심사관이 각 입국자들을 심사하는 데 걸리는 시간 중 최댓값을 구하고, 이 값들을 case마다 비교해서, 가장 최소인 값을 정답으로 판단하려고 했다.

하지만, 이렇게 각 case를 나누는 방법은, 결국 모든 case를 다 해봐야 최솟값을 알 수 있고, 너무 시간도 오래 걸리고, 사실 어떻게 나눠야할 지 감도 오지 않았다.

---

✒️ Solution

우선,

• 10억명이면 사실 선형시간(log n) 으로는 거의 불가능하다고 볼 수 있기 때문에, 로그시간(log n) 으로 풀어야 한다
• 로그 시간이면 보통 => 이진 탐색을 사용한다 !
• 현재
  • 입국자 수 : 최대 10억
  • 심사관이 심사하는데 걸리는 시간 : 최대 10억
  • 심사관들의 수 : 최대 10만 => 이를 기준으로 loop를 돌리는 게 좋을 듯

위 3가지 사항을 바탕으로, 이 문제에 이진 탐색을 어떻게 적용할 지 생각해보면,

• 시간이 지남에 따라 각 심사관들이 몇 명을 처리할 수 있는지를 기준으로,

  특정 시간이 지났을 때, 모든 심사관들이 처리할 수 있는 입국자들 수를 계산하고, 주어진 입국자 수 n을 다 처리할 수 없다면 시간을 더 늘리고, 처리할 수 있다면 시간을 더 줄이는 방식으로 이진 탐색을 진행할 수 있다.

  이를 통해 주어진 입국자 수 n을 처리하게 되는 최소의 시간을 구하면 된다.

• n분이 지났을 때, 각 심사관 당 처리 가능한 입국자 수

  = n / 각 심사관의 심사 시간 으로 구할 수 있다.

즉, 나와 solution의 접근 방식을 비교하면

• my : 각 심사관이 몇 명을 처리할 지 결정 => 총 걸리는 시간을 계산

• solution : 걸리는 시간을 먼저 결정 => 그 시간 안에 각 심사관들이 몇 명을 처리할 수 있는지를 계산

서로 반대 방향으로 접근했음을 알 수 있다.

Binary Search 진행 시, 주의할 점

기본 Binary Search는 특정 값 또는 특정 값의 index를 반환하지만,

현재 우리가 원하는 것은 특정 값을 가지는 index의 최소값 이다.

=> 주어진 입국자 수 n을 처리할 수 있게 되는 최소의 시간 이기 때문이다.

위를 바탕으로 Binary Search 탐색 조건과 return 값을 수정해서 코드를 작성해야 한다.

solution을 바탕으로, 코드를 작성해보았다.

function solution(n, times) {
    
  const sortedTimes = times.sort((a,b)=>a-b); 
  let left = 1;
  let right = sortedTimes[sortedTimes.length-1]*n; // 최대로 흐를 수 있는 시간 => 가장 오래걸리는 심사관이 모든 입국자를 심사할 때 

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

      let testedPeople=0;

      sortedTimes.map((testTime) => {
          return Math.floor(mid/testTime); // 각 면접 심사관이 mid분이 지났을 때 심사할 수 있는 사람 수
      }).forEach((testedPerson) => {
          testedPeople+=testedPerson;
      });

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

  return left;
}

---

➕ 찾아볼 내용

• 탐색 조건에 따라 Binary Search 코드 변형하기