[프로그래머스 레벨3] 입국심사 [Javascript/이진탐색]

문제 유형 : 이진탐색

https://school.programmers.co.kr/learn/courses/30/lessons/43238?language=javascript 

프로그래머스

 

문제 풀이

이진 탐색은 범위가 있어야하고 범위라는 건 시작점(최솟값)과 끝점(최대값)을 알아야 한다. 
times 배열에서 최댓값을 구할 때 sort 대신 Math.max(...배열)을 사용해서 구했다.

sort는 n log n 이지만 Math.max는 n 의 시간복잡도를 가진다.

최솟값은 한 명을 심사하는데 걸리는 시간이 1분이상이므로 1이된다

 

[-----------------------------------------------]

left                   mid                        right

 

이진 탐색 while 문에서 left<= right 등호를 반드시 넣어야 한다.

 

reduce로 풀면 sum을 가독성있게 구할 수도 있다.

const sum = times.reduce((acc, time) => acc + Math.floor(mid/ time), 0)

로직 reduce는 mid분 안에 각 심사관이 처리할 수 있는 사람의 수의 합을 계산하기 위한 로직입니다.
예를 들어, 30분이라면 처리 속도가 7인 심사관은 4명, 처리 속도가 10인 심사관은 3명을 처리할 수 있습니다. 이 경우 그 합이 7이기 때문에 6명을 처리한다면 걸리는 시간을 조금 더 줄일 수 있지 않을까?로 생각할 수 있으니 right를 mid - 1로 줄입니다.
이런 방식으로 걸리는 시간의 최솟값을 찾을 수 있습니다.

 

 

<주의>

left가 right를 넘겨서는 순간 return left를 하면 된다.

 

 

시물레이션

left : 처리에 걸리는 가장 짧은 시간(1분)  <--- 최솟값구하기
right: 처리에 걸리는 가장 오래 걸리는 시간(모두가 최악의 심사관을 만나게 됨)  <-- 최댓값 구하기
mid: 우리가 확인해 볼 임의의 시간

 

n = 6, times = [7, 10] 의 입출력 예시의 경우입니다.

1차 루프 : left = 1, right = 60 mid = 30, sum = 7
2차 루프 : left = 1, right = 29, mid = 15, sum = 3
3차 루프 : left = 16, right = 29, mid = 22, sum = 5
4차 루프 : left = 23, right = 29, mid = 26, sum = 5
5차 루프 : left = 27, right = 29, mid = 28, sum = 6
6차 루프 : left = 27, right = 28, mid = 27, sum = 5
7차 루프 : left = 28, right = 28, mid = 28, sum = 6
8차 루프 : left = 28, right = 27 반복문이 종료되어 left 값을 반환함

 

<<시작>>
테스트케이스: n(입국자 수): 6, times(걸리는 시간): [7, 10]

1차루프 -> 30분(mid)동안 몇 명을 쳐낼 수 있을까?
left: 1, right: 60, mid: 30 sum: 7 (30/7 = 4명, 30/10 = 3명-> 총 7명)
-> n(입국자 수) < sum(처리할 수 있는 사람의 수) : 어라? 조금 더 시간을 줄일 수 있겠는데? -> right 값 옮김

2차 루프 -> 15분(mid)동안 몇 명을 쳐낼 수 있을까?
left: 1, right: 29, mid: 15 sum: 5 (15/7 = 2명, 15/10 = 1명 -> 총 3명)
-> n(입국자 수) > sum (처리할 수 있는 사람의 수) : 어라? 시간이 더 필요한데? -> left 값 옮김

3차 루프 -> 22분(mid)동안 몇 명을 쳐낼 수 있을까?
left: 16, right: 29, mid: 22 sum: 5 (22/7 = 3명, 22/10 = 2명 -> 총 5명)
-> n(입국자 수) > sum(처리할 수 있는 사람의 수) : 어라? 시간이 더 필요한데? -> left 값 옮김

4차 루프 -> 22분(mid)동안 몇 명을 쳐낼 수 있을까?
left: 23, right: 29, mid: 26 sum: 5 (26/7 = 3명, 26/10 = 2명 -> 5명)
-> n(입국자 수) > sum(처리할 수 있는 사람의 수) : 어라? 시간이 더 필요한데? -> left 값 옮김

5차 루프 -> 28분(mid)동안 몇 명을 쳐낼 수 있을까?
left: 27 right: 29, mid: 28 sum: 4 (28/7 = 4명, 28/10 = 2명 -> 6명)
-> n(입국자 수) = sum(처리할 수 있는 사람의 수) : 같을 때엔 right 값을 옮김

6차 루프 -> 28분(mid)동안 몇 명을 쳐낼 수 있을까?
left: 27 right: 28, mid: 27 sum: 5 (27/7 = 3명, 27/10 = 2명 -> 5명)
->n(입국자 수) > sum(처리할 수 있는 사람의 수) : 어라? 시간이 더 필요한데? -> left 값 옮김

7차 루프 -> 28분(mid)동안 몇 명을 쳐낼 수 있을까?
left: 28 right: 28, mid: 28 sum: 4 (28/7 = 4명, 28/10 = 2명 -> 6명)
-> n(입국자 수) = sum(처리할 수 있는 사람의 수) : 같을 때엔 right 값을 옮김

8차 루프 : left>right 이므로 루프를 더이상 돌지 않고 left 값 출력

 

전체코드

function solution(n, times) {
    var sum = 0;
    // 최솟값
    let left = 0;
    // 최대값 : 가장 오래 걸리는 상담원한테 사람들이 다 가는 경우 *time를 sort해서 찾아도 된다
    let right = n * Math.max(...times) ; 
    // = 꼭 들어가야 한다
    while(left<=right){
        // 소수점 버리기
        const mid = Math.floor((left+right)/2);
        let count = 0;
        // 해당 mid 시간동안 입국심사원이 심사가능한 최대 인원 수
        times.forEach((it) => {
            count += Math.floor(mid/it)
        })
        
        // 해당 인원수를 찾은 경우
        //if(count === n) return mid;
        
        // mid 값을 줄어야 할 때 => mid 왼쪽 이동
        // 등호 필수 : 우린 최소값(left)을 찾아야 하기 때문에 mid 값을 줄여도(right를 왼쪽으로 이동해도)값이 유지되는지 
        if(count >= n){
            right = mid - 1
        // mid 값을 늘려야 할 때 => mid 오른쪽 이동
        }else {
            left = mid + 1
        }    
    }
    return left;
}