🔎 입국 심사

❓ 문제링크

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

📄 제출 코드

function solution(n, times) {
    times.sort((a, b) => { return a - b });
    let left = 1;
    let right = n * times[times.length - 1];
    let answer = right;
    while (left <= right) {
        console.log(`left : ${left}, right :${right}`)
        let mid = Math.floor((left + right) / 2);
        console.log(`mid : ${mid}`);
        let cnt = 0;
        console.log(`before cnt : ${cnt}`);
        times.forEach(value => {
            cnt += Math.floor(mid / value);
            console.log(`after cnt: ${cnt}`)
            if (cnt >= n) {
                answer = Math.min(mid, answer);
                return;
            }
        });
        console.log();
        cnt >= n ? right = mid - 1 : left = mid + 1;
    }


    return answer;
}

let n = 6;
let times = [7, 10];

console.log(solution(n, times));

이번 문제는 이분탐색을 이용하여 푸는 문제다.
우선 이분탐색이란 탐색 기법중에 하나로 원하는 탐색범위를 두 부분으로 분할해서 찾는 방식이다. 이분 탐색을 하는 방법은 left , right , mid 값으로 탐색을 하고, mid의 값은 (left + right)/2 으로 잡아주고 우리가 검색하고자 하는 값과 mid 값을 비교한다.

먼저 times를 낮은값부터 정렬하고, left에 시작값, right에 최대값을 넣어놓습니다. 최대값은 n명이 전부 가장 긴 시간을 들어가면 최대값이 됩니다.
left가 right보다 커질때 까지 반복을 합니다.
중간값 mid를 구하고, 그 시간으로 검문 할 수 있는 사람수 '(중간값 / 시간)'을 더해줍니다. 그렇게 cnt가 n보다 큰지 검사하고, answer를 도출 해냅니다.
다음 반복으로가기전 cnt가 n보다 크거나 같으면 right를 1줄여서 다시돌고, 아니면 left에 +1해서 다시 반복합니다.
해당 과정을 console로 찍어보면 아래와 같습니다.

eft : 1, right :60
mid : 30
before cnt : 0
after cnt: 4
after cnt: 7

left : 1, right :29
mid : 15
before cnt : 0
after cnt: 2
after cnt: 3

left : 16, right :29
mid : 22
before cnt : 0
after cnt: 3
after cnt: 5

left : 23, right :29
mid : 26
before cnt : 0
after cnt: 3
after cnt: 5

left : 27, right :29
mid : 28
before cnt : 0
after cnt: 4
after cnt: 6

left : 27, right :27
mid : 27
before cnt : 0
after cnt: 3
after cnt: 5

28