[프로그래머스]입국심사 - 자바스크립트 | 이분탐색 | Lv.3

문제

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

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

 

풀이

function solution(n, times) {
    times.sort((a, b) => a - b);
    let min = times[0];
    let max = n * times[times.length -1];

    while(min <= max){
        const mid = Math.floor((min + max) / 2);
        const count = times.reduce((acc, curr) => acc + Math.floor(mid / curr), 0); // 한 사람당 몇명 할 수 있는지
        console.log(min, max, mid, count);
        count >= n ? max = mid - 1 : min = mid + 1;
    }
    return min;
}

 

1. 이분탐색을 위해서는 정렬된 배열이 필요하다.

times.sort((a, b) => a - b);

2. 가장 최소로 걸리는 시간(min)과 최대로 걸리는 시간(max)를 먼저 구해준다.

let min = times[0];
let max = n * times[times.length -1];

3. (최소+최대)/2로 시간의 중간값(mid)을 구한다.

const mid = Math.floor((min + max) / 2);

4. times를 돌면서 각 심사관 한 사람당 mid 시간동안 몇명을 심사할 수 있는지 계산(Math.floor(mid / curr))해서 총합을 구한다. (acc에 누적해줌)

const count = times.reduce((acc, curr) => acc + Math.floor(mid / curr), 0);

5. 만약, mid시간 동안 검사할 수 있는 인원의 총 수(count)가 주어진 n명보다 많거나 같을 경우,

• max를 mid 이전으로 만들어 왼쪽 공간을 탐색 공간으로 정한다.

n명보다 적을 경우,

• min을 mid 다음으로 만들어 오른쪽 공간을 탐색 공간으로 정한다.

count >= n ? max = mid - 1 : min = mid + 1;

그럼 최종 min값이 n명을 심사하는 데 걸리는 최소 시간이다.

 

---

 

느낀점

이분탐색을 그냥 왼쪽 오른쪽 조절해서 탐색하는 용, 배열에 있는 값에서 찾고자 하는 값만 찾는 알고리즘이라고 생각했었는데, 이 문제로 이분탐색을 어떻게 활용하면 되는지 알 것 같다.
처음에는 times 배열만으로 어떻게 왼쪽 오른쪽 탐색 공간을 잡을 지 생각해봤는데..

무조건 주어진 배열에서 mid값을 구해서위치만 조절하는 것이 아닌, 문제를 활용해서 내가 직접 최소값과 최대값을 지정해주고 탐색할 공간의 범위를 생각해보자. 그렇게 내가 정한 공간에서 중간값을 변경하면서 조건을 따져보는 식으로 풀면 될거다..!