42238: 입국심사[이분탐색]

Link : programmers.co.kr/learn/courses/30/lessons/43238

---

1. 문제

• n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.
  처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
  모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.
  입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

---

2. 문제의 조건

• 1 <= n <= 1,000,000,000
• 1 <= times <= 1,000,000,000
• 1 <= 심사관 <= 100,000

 

---

3. 문제 접근

• 시간 복잡도
  
  범위가 10억으로 어마무시합니다. 대부분 이런문제는 log n으로 풀어야만 합니다. 탐색에 log n이 걸리는 것은 이분탐색밖에 없습니다.

 

• 아이디어
  
  해당 문제의 힌트가 "이분탐색"이고 이분탐색으로 이러한 조건을 찾는 경우 "파라메트릭 서치" 기법이 있습니다. n의 범위를 이분탐색으로 조정하면서 옳바른 값을 검사하는 방법입니다.
  
  예제로 주어진 값 "6, [7, 10]"을 보면, 최악의 경우 60분동안 검사를 진행하는 경우를 보실 수  있습니다.
  왜냐하면, 1명 검사하는데 10분 가진 검사관이 6명을 전부 검사 하였을 경우입니다. 범위는 0~60으로 잡고 이분탐색을 진행합니다.
  
  30분으로 예를 들면
  idx가 0인 7은 30분동안 4명을 검사할 수 있고
  idx가 1인 10은 30분동안 3명을 검사할 수 있습니다.
  총 7명을 검사할 수 있는 시간인데 n는 6이므로 30분은 너무 과도한 시간인것을 파악할 수 있습니다. 그럼
  0 ~ 29 까지 범위를 잡고 이분탐색을 진행합니다.
  
  14분으로 예시를 들면
  idx가 0인 7은 15분 동안 2명을 검사할 수 있고
  idx가 1인 10은 15분 동안 1명을 검사할 수 있으므로
  3명밖에 검사를 하지 못합니다.
  그럼 범위를 늘려 15~29 범위를 잡습니다.
  
  한번 더 22분으로 예시를 들면
  idx가 0인 7은 22분동안 3명을 검사할 수 있고
  idx가 1인 10은 22분동안 2명을 검사할 수 있습니다.
  5명밖에 검사를 하지 못하므로 s부분을 늘려갑니다.
  
  이런식으로 n이 6으로 되는 조건을 찾으면서, 최소여야합니다.

 

---

4. 풀이 방법

• 입국 심사관 들을 시간(오름차순)으로 정렬합니다.
• 탐색 범위를 알기위해 제일 긴 입국 심사관을 저장합니다.
  탐색 범위는 10억 * 10억 입니다. 그러므로 찾아야 할 최솟 값을 10억 * 10억으로 맞춰 놓습니다.
• 탐색 범위 mid를 정해줍니다.
• 만약 n과 검사할 수 있는 값이 같을 경우, 최소보다 작으면 최소 값을 저장합니다.
• 만약 값이 n보다 크면 e를 줄여 값을 줄이고
  만약 n보다 값이 작으면 s를 늘려 값을 올립니다.

 

---

5. 소스코드

• cjw-git.tistory.com/100

 

---

 

cjw.git@gmail.com