[프로그래머스] 입국심사 Java 풀이 및 해설

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

프로그래머스

 

풀이 방법

우선순위 큐 방식을 생각했지만 O(N)으로 시간초과가 난다. 더 빠른 방법이 있을까...

 

이걸 어떻게 이진탐색으로 푼다는건지 신기하다..

 

이진 탐색 풀이 방법은 다음과 같다.

1. left : 모든 사람들을 심사하는게 걸리는 최소 시간
2. right : 모든 사람들을 심사하는게 걸리는 최대 시간
3. mid : 심사하는데 걸리는 총 시간
4. cnt : mid 시간동안 심사 받을 수 있는 최대 사람 수

 

mid 시간 동안 최대 cnt명을 심사할 수 있다.

cnt가 n보다 작으면

mid 시간동안 실제 사람 수만큼 검사를 하지 못한것이므로

mid 시간을 늘려야한다.

 

cnt가 n보다 크다면

mid 시간동안 n보다 더 많은 사람들을 검사할 수 있었던거니

mid 시간을 줄여야한다.

 

cnt가 n과 같으면 mid 시간동안 n명을 검사할 수 있다는 뜻이다.

여기서 break하지 않은 이유는 더 적은 시간으로 n명을 검사할 수도 있기 때문이다.

 

전체 코드

import java.util.*;
class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        
        Arrays.sort(times);
        
        long left = 0;
        long right = times[times.length-1] * (long)n; 
        // "*" 연산에 long 타입이 없으면
        // 연산 결과를 int로 해석 저장하고 long으로 변환하기에 올바른 연산 결과가 아님
        // 연산 결과를 long으로 해석 저정하기 (long)n 해줘야함.
        
        while(left <= right) {
            
            long mid = (left + right) / 2;
            long cnt = 0; // 심사 받을 수 있는 사람
            for(int i=0; i<times.length; i++) {
                cnt += mid / times[i];
            }
            
            // 받을 수 있는 사람이 실제 사람 보다 작으면 시간을 더 늘려야함.
            if(cnt < n) {
                left = mid + 1;
            } else {
                answer = mid;
                right = mid - 1;
            }
            
        }
        
        return answer;
    }
}