[이진 탐색] 입국심사

Problem. 입국심사

---

Link.

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

프로그래머스

---

Problem.

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다.

각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

 

처음에 모든 심사대는 비어있습니다.

한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다.

가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다.

하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수 도 있습니다.

 

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

 

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때,

모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성하시오.

 

제한사항

1. 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하

2. 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하

3. 심사관은 1명 이상 100,000명 이하

 

입출력 예시

// case#1
n = 6;
times = [7, 10];
return = 28

---

In Details.

Case#1

n = 6, times = [7, 10]

 

Code#1. left와 right 초기화

left는 입국심사에 걸리는 시간이 가장 적은 1을 할당

right는 입국심사에 걸리는 시간이 가장 긴 Math.max(...times) * n을 할당

(심사 시간이 가장 오래걸리는 심사관에게 모든 사람이 심사를 받는 경우를 가정)

let left = 1;
let right = Math.max(...times) * n;

 

Code#2. while문

이진 탐색의 개념에 따라 

left가 right보다 커질때까지 while문을 실행

while (left <= right) {
	// 중앙값 계산
    let mid = Math.floor((left + right) / 2);
    // mid / time => 특정 심사원이 심사할 수 있는 인원 수
    // times.reduce() => 각 심사원이 심사할 수 있는 인원 수를 합하기 위한 함수
    // sum => 심사원들이 mid 시간안에 심사한 총 심사원 수
    let sum = times.reduce((acr, time) => acr + Math.floor(mid / time), 0);
	
    if (sum < n) {
    	// 심사한 총 심사원(sum)이 심사해야할 수(n)보다 작은 경우 (최소값을 UP)
        left = mid + 1;
    } else {
    	// 심사한 총 심사원(sum)이 심사해야할 수(n)보다 큰 경우 (최대값을 DOWN)
        right = mid - 1;
    }
}

 

Code#3. left 값 반환

이진 탐색을 로직을 만족했을 때의 left 값이 답이 된다.

return left;

---

My Answer. 

function solution(n, times) {
    // 심사에 소요되는 시간의 최솟값
    let left = 1;
    // 심사에 소요되는 시간의 최대값
    // => 입국심사를 받는 모든 사람이 심사 시간이 가장 많이 걸리는 심사관한테 심사를 받는 경우
    // (최대 심사 시간) x (입국심사를 받는 사람의 수)
    let right = Math.max(...times) * n;
    
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        let sum = times.reduce((acr, time) => acr + Math.floor(mid / time), 0);
        if (sum < n) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return left;
}

---

References.

• 코딩테스트 광탈 방지 A to Z: JavaScript (이선협)

---

For Developer. 

• 잘못되거나 부족한 부분이 있다면 언제든지 댓글 부탁드립니다 :)