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

🧾 목차

1. 문제 설명

2. 문제 풀이

3. 전체 코드

---

1. 문제 설명

 

n명이 입국심사를 위해 줄을 서서 기다리고 있는데, 모든 사람이 심사를 받는데 걸리는 시간의 최소값을 구하는 문제

각 심사원이 한 명을 심사하는 데 걸리는 시간은 모두 다르며, times 배열을 통해 주어진다.

 

입출력

6명이 통과해야한다.

총 2명의 심사원은 심사를 하는데 각각 [7분, 10]분이 걸린다.

 

1) 가장 첫 두 사람은 바로 심사를 하러 간다.

2) 7분이 되었을 때, 세번 째 사람이 심사를 받는다.

3) 10분이 되었을 때, 네번 째 사람이 심사를 받는다.

4) 14분이 되었을 때, 다섯번 째 사람이 심사를 받는다.

5) 20분이 되었을 때, 심사대가 비지만 거기서 심사를 받지 않고 21분이 되었을 때 심사를 받는다.

6) 28분이 되었을 때, 모든 사람의 삼사가 끝난다.

 

제한사항

 

최대로 걸리는 시간 계산

e.g. 어떤 경우? 

1) 승객: 10^9

2) 심사관이 승객을 심사하는 데 걸리는 시간 : 10^9

3) 심사관: 1

최대 입국 심사 대기열 x 한 심사관이 한 명을 심사하는 데 걸리는 최대 시간 = 10^18 (시간 초과!!)

 

📌 팁

제한사항이 이 문제처럼 엄청 클 때는 범위를 줄이기 위하여 이분탐색 진행한다.

---

2. 문제 풀이

최대 입국 심사 대기열 x 한 심사관이 한 명을 심사하는 데 걸리는 최대 시간 = 10^18 (시간 초과!!)

따라서, 이분 탐색으로 범위를 좁혀야한다.

그럴 경우, 선형 탐색으로는 O(n) 만큼 발생한 시간을 O(logn) 만큼 줄일 수 있다.

e.g. log(10^18) = 약 60번

 

1. 초기화

left, right를 최소 시간, 최대 시간으로 초기화하였다.

 

2. 이분탐색 반복문

1) 중간값을 계산한다.

2) 패스한 승객 수를 계산한다.

3) 범위를 조정한다.

  3-1) 패스한 승객이 요구한 수보다 많거나 같다면 👉 정답이 중간값보다 낮다는 의미

  3-2) 패스한 승객이 요구한 수보다 적다면 👉 정답이 중간값보다 높다는 의미

 

3. 시간복잡도

O(MlogN) 

(M: 심사관의 수, N: 최대로 걸리는 시간)

 

---

3. 전체 코드

MAX_PASSENGER = 1000000000; // 최대 입국 심사 대기열
MAX_MINUTE_BY_STAFF = 1000000000; // 최대 각 심사관이 한 명을 심사하는데 걸리는 시간

function solution(n, times) {
  var [left, right] = [1, MAX_PASSENGER * MAX_MINUTE_BY_STAFF]; // 최소 걸리는 시간, 최대 걸리는 시간

  while (left <= right) {
    var mid = Math.floor((left + right) / 2); // 중간 값 계산

    // 패스한 승객 수 계산
    var pass = 0;
    for (let i = 0; i < times.length; i++) {
      // 중간 시간을 기준으로 패스할 수 있는 승객의 수를 구함
      pass += Math.floor(mid / times[i]);
    }

    // 범위 조정
    if (pass >= n) {
      // 패스한 승객이 요구한 수보다 많다면
      right = mid - 1; // 최대 시간을 줄임
    } else {
      left = mid + 1; // 최소 시간을 늘림
    }
  }

  return left; // 최종적으로 필요한 최소 시간 반환
}

---