[PRG] 43238. 입국심사 - Java

📝 문제

문제 | 프로그래머스 43238. 입국심사

💡 풀이 과정

⛓ 사용한 알고리즘 : 이분탐색

n의 범위가 굉장히 크기 때문에 모든 경우의 수를 살피는 방법은 사용할 수 없다. 따라서 효율적인 탐색을 위해 이분 탐색을 이용하여 정답을 찾았다.

우선 이분탐색을 위해 times 배열을 정렬한다. 이후 최솟값과 최댓값을 지정해주는데, 최솟값은 0 이고, 최댓값은 최악의 경우인 가장 시간이 오래걸리는 심사위원이 n명을 모두 검사할 경우 이다. 즉, 오름차순으로 정렬한 times 배열의 가장 마지막 원소에 n 을 곱한 수가 되는 것이다.

양쪽 값을 세팅했다면 최솟값이 최댓값을 뛰어넘을 때까지 반복해서 이분 탐색을 진행한다. 최솟값과 최댓값의 중간값을 구해서 mid 변수에 넣는데, 이 때 mid 는 심사하는데 걸리는 시간이 된다.

이제 이 시간 안에 모든 승객을 심사할 수 있는지를 계산해줄 수 있다. 각 심사위원별로 해당 시간 내에 검사할 수 있는 인원을 세서 sum 변수에 모두 더한 뒤 n 과 비교하면 된다. 이 때 sum 이 n 이상일 경우에는 해당 시간 내에 심사가 가능하다는 뜻이므로 최댓값을 mid-1 로 변경하고, 그렇지 않은 경우는 해당 시간 내에 심사가 불가능하다는 뜻이므로 최솟값을 mid+1 로 변경해준다.

탐색이 모두 종료된 후의 최솟값이 바로 입국 심사를 끝낼 수 있는 최단 시간이 된다.

코드

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        
        Arrays.sort(times);
        
        long l=0,r=(long)times[times.length-1]*n;
        
        while(l<=r) {
            long mid = (l+r)/2;
            long sum = 0;
            
            for(int t: times) {
                sum += mid/t;
            }
            
            if(sum>=n) {
                r = mid-1;
            } else {
                l = mid+1;
            }
        }
        
        return l;
    }
}