프로그래머스 입국심사

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

문제 풀이

n = 6, times = [7, 10]인 경우

1 2 3 4 5 6

0 0 7 10 14 20 -> 총 30분 이지만 마지막 6번째검사 하는사람이 1분만 기다리고 21분에 검사를 받게되면 28분에 검사가 완료됨

즉, 최종 결과는 30분이 아니라 28분이 나와야 함

---

이분 탐색을 이용하여 문제를 접근하였고

1. times에 존재하는 가장 작은 값 * (n + 1)을 최대 시간이라 지정 (위 예시에서는 0 0 7 14 21 28로 35라는 값이 나옴)

2. 이분 탐색 알고리즘을 이용해 최소 time을 구해야 함

3. 특정 시간에 n명의 사람이 모두 검사 받을 수 있는 로직

-> value(특정 시간)이 주어졌을 때 times에 존재하는 시간으로 나눈 몫들의 합이 n보다 클 경우 value시간안에 n명이 처리가 가능하다는 의미

-> ex) value가 30이고 times가 [7, 10] 인 경우에 7분텀으로 검사할 수 있는 사람 수 + 10분 텀으로 검사할 수 있는 사람 수를 합한 값이 n보다 큰 경우 value시간안에 검사가 가능하다는 의미 ( 30 / 7 + 30 / 10 = 7로 n=6보다 큼, 따라서 검사 가능)

4. 위의 로직과 이분탐색을 이용하여 최소 시간을 구함

5. (left를 설정할 경우 left 값을 mid로 할 경우 특정한 경우에 계속 반복을 하게됨) -> 위 예시에서 left=27, right=28인 경우 mid값이 27이 나오고 검사가 불가능해 left를 계속 27로 만들어 반복문이 종료되지 않음

-> 따라서 left와 mid가 같은 경우는 반복문이 더 이상 동작하지 않도록 처리를 해줘야 함.

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

    function canPass(value) {
        let people = 0;
        people = times.reduce((acc, cur) => acc + Math.floor(value / cur), 0);
        return people >= n;
    }
    
    let left = 0;
    let right = Math.min(...times) * (n + 1);
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (canPass(mid)) {
            right = mid;
            answer = Math.min(answer, mid);
        } else {
            if (left === mid) break;
            left = mid;
        }
    }
    
    return answer;
}

---

결론

n과 times의 크기를 고려했을 때 최소 시간을 구하는 로직은 이분탐색 알고리즘을 사용하여 접근하는 것이 맞음.

또한, 이분 탐색의 특정 값(mid)로 검사가 가능한지에 대한 로직을 잘 생각하는 것이 중요

-> 이분탐색이여도 검사하는 로직을 생각하지 못한다면 문제를 해결할 수 없음.