99클럽 코테 스터디 3일차 TIL (43238 입국심사)

문제

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

 

---

 

학습 키워드

• 이진 탐색

 

시도

• 20분 동안 시간초과를 하지 않으면서 동작가능한 로직을 생각하지 못했고, 다른 사람 해석을 참고했다.
• (성공) 주어진 시간을 탐색하면서 그 시간동안 각 심사관들이 몇 명의 고객들을 처리했는지 계산하고, 기존 대기자의 수보다 많은 사람들을 처리했다면 그 범위를 좁혀가면서 가장 적은 시간동안 대기자들을 모두 처리했는지 계산하는 방법으로 풀었다.

 

풀이

이진탐색을 하기 위해서 right의 값은 가장 오래 걸리는 심사 시간 * n을 해서 모든 경우를 전부 탐색할 수 있도록 설정했다.

자료형들을 long으로 하는 이유는 심사하는데 걸리는 시간의 최대값이 1,000,000,000이고, 입국 심사를 기다리는 사람은 최대 1,000,000,000이기 때문에 int 대신 long을 사용해야 한다.

long solution(int n, int[] times) {
    long maxTime = Long.MIN_VALUE;
    for (int time: times) {
        maxTime = (long) Math.max(maxTime, time);
    }
    binarySearch(n, times, 0L, maxTime * n);
    return answer;
}

 

left, right, middle은 현재 시간으로, 그 시간 동안 모든 심사관들이 대기자를 처리한다면 최대 몇 명까지 처리할 수 있는지 계산한다.

만약 모든 대기자들을 처리할 수 있다면 answer에 저장하면서 그 범위를 좁혀 나가며 최적의 값을 찾는 방식이다.

void binarySearch(int numberOfWaiting, int[] times, long left, long right) {
    while (left <= right) {
        long middle = (left + right) / 2;
        long numberOfProcessed = 0;
        for (int time: times) {
            numberOfProcessed += middle / time;
        }
        if (numberOfProcessed >= numberOfWaiting) {
            answer = (long) Math.min(answer, middle);
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }   
}