[프로그래머스][LEVEL3] 입국심사

# 문제 원문

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

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

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

입출력 예

n / times/ return

6

[7, 10]

28

 

출처

 

# 문제 풀이

 

입력 받은 n명을 times를 통해서 소요하는 시간을 구하는 문제이다. 이분 탐색 카테고리에 속해있으며, 기존 문제들이 단순히 배열상의 요소의 양방향 탐색이였다면 이건 해당 배열상의 요소를 임의의 가중치를 통해서 재가공한 후 탐색하는 응용을 해야한다. 이분탐색이라는 개념에 대해서 자세히 이해하고 있지 않다면 어려움을 느낄 문제로 보인다.

개인적으로는 어렴풋한 이해 정도로 알고 있던 내용을 찾아서 복습해야 할 필요가 있었다. 최대값과 최소 값 두 방향에서 탐색을 하고, n과 mid 값으로 구해진 인원수를 기준으로 범위가 조정 되는 점이 직관적이지 않아서 고생했다.

 

# 솔루션 플로우

1. 입력 받은 times 배열를 정렬시킨다.

2. 최소값 (left)를 0을 주고 최댓값(가장 큰수 * n)을 구한다.

3. 최소 시간이 최대 시간보다 커질때 까지 반복한다.

4. 두 지점의 중심(pivot || mid)을 (left + right) / 2 로 구한다.

5. 구해진 mid를 times 각 요소로 나누어서 해당 시간 동안 검사 하는 총 인원 수 (headCount)를 구한다.

6. 구해진 headCount 를 기준으로 인원이 많으면 최댓값 범위를 mid - 1로 주고, 적으면 최솟값을 mid + 1해준다.

7. 반복이 끝난 후 구해진 최소 소요 시간 left을 반환한다.

1. 이분탐색

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

    while (left <= right) {
        const mid = parseInt((left + right) / 2);
        const headCount = times.reduce((result, current) => result + parseInt(mid / current), 0);
        headCount >= n ?
            right = mid - 1 :
            left = mid + 1;
    }
    
    return left;
}