[Lv3] 입국심사

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

코딩테스트 연습 - 입국심사

---

일 처리 시간이 다른 입국 심사대에서 n명을 처리하는 데 걸리는 최소 시간 구하기

 

사람을 입국 심사대에 넣는게 아니라, 시간이 주어질 때 입국 심사 가능한 최대 인원을 구한다. 즉,

n명이 입국 심사대를 통과하는 최소 시간 찾기가 아니라, 특정 시간에서 통과할 수 있는 최대 인원을 구함으로써 타겟으로 하는 인원 n을 만족할 때의 시간을 구한다.

 

Binary Search에 있어서 부등호에 의한 혼란이 좀 있어서, 이를 이해하기 위한 예시를 들어봄.

 

가령, n = 8이고, times = [3, 7, 10]으로 주어진 경우에 solution을 구한다고 하자. 참고로 답을 미리 말하자면 15분이고, 사람 8명을 통과하는데 걸리는 '시간의 경우의 수'는 15분 16분 17분이다. 기재된 정보들을 가지고 부등호에 따라서 어떤 식으로 solution이 나오는지 아래와 같이 볼 수 있다.

 

+ 참고로 최대 시간은 80분이 아닌 30분으로 가정함. 80분으로 하든 30분으로 하든 정답인 15에 가까워지기때문에 별로 안중요함.

답안에 작성된 부등호대로 숫자를 따라가다 보면 위와 같이 정답이 return이 된다.

 

그리고 이를 큰 그림에서 보면, 

이게 중요한데, 이를 글로써 설명하자면

 

초기 while문에서 0과 30의 중간값인 15에서 정답인 8이 나오지만, 이를 지나치고 right는 14가 된다.

(정답을 지나치다니 이게 무슨일일까?)

left 0과 right 14로부터 mid 7을 구하고 left는 8, right은 14가 된다.

left 8과 right 14로부터 mid 11을 구하고 left는 12, right은 14가 된다.

left 12와 right 14로부터 mid 13을 구하고 left는 14, right는 14가 된다.

left 14와 right 14로부터 mid 14를 구하고 left는 15, right은 14가 된다.

left > right이므로 while문 탈출 후 left를 return 한다.

 

즉, mid가 정답인 15를 만나게 되면 right = mid - 1을 하게 되고, left와의 중간값을 계속해서 구해올라오면서 left가 15에 도달하도록 동작하는 코드이다.

 

근데 만약 여기서 부등호 딱 하나만을 바꿔서 동작시키면, 정 반대방향으로 동작하게 된다.

 

18을 return하게 되고, 아까와 마찬가지로 이를 큰 그림에서 본다면 아래와 같다.

부등호 하나 차이로 n = 8을 만들 수 있는 15분 16분 17분 중, 가장 오랜 시간이 걸리는 17분을 구하기 위한 코드처럼 작동하게 된다.

 

 

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

프로그래머스

var floor = n => Math.floor(n);

function solution(n, times) {
    var answer = 0;

    return s(n,times);
}
function s(n, times ) {
    var min =0 , max = n * Math.max.apply(null, times);
    while (min <= max) {
        var mid = floor((min + max) / 2);
        var maxInMid = times.reduce((acc,cur)=>acc += floor(mid/cur) , 0);
        if( n <= maxInMid) {
            max = mid -1;
        } else {
            min = mid + 1;
        }
    }
    return min;
}