[프로그래머스 자바스크립트] ‘입국심사’ 풀어보기

프로그래머스의 코딩테스트 문제 → 알고리즘 고득점 Kit → 이분탐색 카테고리에서 풀었다.

이분탐색이라는 카테고리 안에 있는 문제인 것은 알았지만, 도대체 왜 이 문제가 이분탐색을 활용해야하는지 이해하지 못하고 삽질만 계속하다가 다른 분들의 풀이를 보고 겨우겨우 풀 수 있었다.

 

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43238

풀이

우리가 구해야하는 것은 ‘모든 사람이 심사를 받는데 걸리는 시간의 최솟값’이다.

n은 입국심사를 기다리는 사람 수이며, 배열 times에는 각 심사관이 한 명을 심사하는데 걸리는 시간이 담겨있다.

 

만약 ‘모든 사람이 심사를 받는데 걸리는 시간의 최솟값’을 안다면(answer라고 하자),

심사관 A가 한 명을 심사하는데 걸리는 시간을 answer로 나눈 값 = A가 심사한 사람의 수이다.

즉, times를 순회하며 심사관들이 심사한 사람들의 수의 합이 n과 같은지 찾아보면 된다.

 

이제 여기서 이분탐색을 어떻게 사용할까?

 

일단 times 배열을 오름차순으로 정렬한다. (const sortedTimes = times.sort((a, b) => a - b); 을 사용한다)

 

left = 1, right = sortedTimes의 가장 오른쪽 값(가장 큰 값)으로 놓는다.

즉, right는 가장 느리게 심사받을 때의 시간이다.

 

그리고 이분탐색을 진행한다. (left가 right보다 작거나 같을 동안 무한반복)

mid = Math.floor((left + right) / 2)로 구하고, sortedTimes를 순회하면서 각 요소들을 mid로 나누어 사람들의 수를 구한다. 그리고 그

 

사람들의 수를 변수 people에 더한다.

people이 n보다 크거나 같다면(n보다 많거나 같은 수의 사람들을 심사했다면) → right = mid - 1로 설정한다.

people이 n보다 작다면(n보다 더 적은 사람들을 심사했다면) → left = mid + 1로 설정한다.

 

이렇게 범위를 좁혀나가다가, right보다 left보다 작게 되어 while문을 벗어나면 n명을 심사할 때의 최소 시간인 left를 return한다.

(부연설명을 하자면, while문이 끝나는 시점에서 left는 "n명을 심사할 수 있는 가장 작은 시간"을 가리킴)

 

예시를 들어보자.

n=6, times=[7,10]인 경우를 가정한다면,

left=1, right=60, mid=30

• 심사=6명 (30/7=4, 30/10=3)
• right=29

left=1, right=29, mid=15

• 심사=3명 (15/7=2, 15/10=1)
• left=16

left=16, right=29, mid=22

• 심사=6명 (22/7=3, 22/10=2)
• right=21

left=16, right=21, mid=18

• 심사=4명 (18/7=2, 18/10=1)
• left=19

left=19, right=21, mid=20

• 심사=5명 (20/7=2, 20/10=2)
• left=21

left=21, right=21, mid=21

• 심사=5명 (21/7=3, 21/10=2)
• left=22

left=22, right=21

• while문 종료
• left=22 반환

22분이 6명을 심사할 수 있는 최소시간이다.

 

(여기서 n이 people과 같은 값일 때에도 계속 루프가 진행되어야할까?

→ 최소값을 찾기 위해서. 현재 mid로 n명을 심사할 수 있다고 해도, 더 작은 시간으로도 n명을 심사할 수 있을 가능성이 있기 때문에 right를 줄여가며 계속 탐색해야 한다.)

---

코드

function solution(n, times) {
    const timesLength = times.length;
        
    const sortedTimes = times.sort((a, b) => a - b);

    // 이분탐색을 통해 모든 사람이 심사를 받는데 걸리는 최소한의 시간을 찾자
    // left, right 초기값 설정
    // 여기서 right는 가장 오래걸리는 시간
    
    let left = 1;
    let right = n * sortedTimes[timesLength - 1];
    let mid = Math.floor((left + right) / 2);

    
    // left가 right보다 작거나 같을 동안에는 무한반복
    while(left <= right) {
        mid = Math.floor((left + right) / 2);

        
        // 사람의 수 people 선언
        let people = 0;
        
        // sortedTimes을 순회하면서 mid에 sortedTimes의 요소를 나눈 값을 people에 더해준다
        // mid에 sortedTimes의 요소를 나눈 값 -> mid 동안 해당 time이 심사한 사람들의 수
        for(let time = 0; time < timesLength; time++) {
            people += Math.floor(mid / sortedTimes[time]); 
        }
        
        // 만약 같거나 많은 사람들을 심사했다면
        if(people >= n) {
            right = mid - 1;
            
        }
        // 만약 더 적은 사람들을 심사했다면
        else {
            left = mid + 1;
        }
    }
    
    return left;
    

}