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

문제

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

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

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

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

제한사항

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

풀이

모든 입국심사 대기자를 모두 심사하는데 걸리는 최소시간을 구하는 문제입니다.

사람을 중심으로 계산을 할 경우 너무 많은 시간이 소요되기 때문에 문제를 풀 수 없습니다. 따라서 역으로 시간을 중심으로 그 시간내에 심사관이 몇명을 처리할 수 있는지 계산하는 방식으로 푸는 방식을 선택하여 풀었습니다.

제가 사용한 방식은 아래와 같습니다.

1. 시간의 범위를 줄여주는 작업을 하기위해 먼저 검사관의 처리 속도를 오름차순으로 정렬합니다.
2. 예상할 수 있는 최소 최대 시간을 구합니다.
   
   1. 최소 = 가장 빨리 처리하는 사람이 1명을 처리하는 시간
   2. 최대 = 가장 느리게 처리하는 사람이 모든 입국자를 처리한 시간 / 검사관 수 = 가장느린처리속도 * 입국자수 / 검사관수
   3. 제한사항에 따라 모든 값들이 int의 범위를 벗어날 가능성이 존재하기 때문에 long으로 캐스팅하여 오버플로우에 대비합니다.
3. 최소 최대 시간을 중심으로 이분탐색을 하며 검색 가능한 사람의 수를 계산합니다.
   1. 이 때, 해당 계산 방식에 예외사항이 존재합니다.
   2. 기본예제 6, {7, 10}을 기준으로 계산을 해보면 28초일때도 6명이 계산되지만 29초일 때도 6명이 계산되어 나옵니다.
      1. 29초일 때 29 / 7 = 4, 29 / 10 = 2가 되기 때문에
   3. 따라서 원하는 인원수가 나왔다 하더라도 최소 값이 아닐 수 있습니다. 따라서 이분탐색시 같은 결과가 나왔다고 return하지 않고  end 값을 줄여가며 탐색을 계속 진행합니다.

public long solution(int n, int[] times) {
    Arrays.sort(times);
    long start = times[0];
    long end = (long)n * times[times.length - 1] / times.length;
    long mid, result;
    long answer = start;

    while(start <= end) {
        mid = (start + end) / 2;
        result = progressedImmigration(times, mid);
        if (result < n) {
            start = mid + 1;
        } else if (result >= n) {
            answer = mid;
            end = mid - 1;
        }
    }

    return answer;
}

private long progressedImmigration(int[] times, long time) {
    long n = 0;
    for (int value : times) {
        n += (time / value);
    }

    return n;
}

결과