[프로그래머스] 입국심사 (Java)

문제

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

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

 

풀이

이분탐색을 이용해서 풀어야 하는 문제이다. 

결과 값이 크기 때문에 타입에 유의해야 한다.

아래와 같이 초기화 한다. 

심사의 최대 시간 =  최소 심사시간 * n 

심사의 최소 시간 = 최소 심사시간 

 

그리고 이분탐색을 진행한다. 

mid값을 총 걸리는 시간이라고 가정한다면,

mid값/심사시간 = 해당 심사관이 심사하는 사람의 수가 된다. 

그리고 모든 심사관의 수를 합하면 mid시간 동안 심사한 사람의 총 인원이 구해진다. 

이 인원이 n이 되는 최소 mid시간을 찾는 것이 목표이다. 

 

소스코드

import java.util.*;
class Solution {
    public long solution(int n, int[] times) {    
        Arrays.sort(times);
        
        // 심사 최소 시간
        long L =  times[0];
        // 심사 최대 시간
        long R =  times[0]*(long)n;
        
        long minVal = 0;
        
        while(L <= R){
            long mid = (L+R)/2;
            // 여기서 mid는 총 걸리는 시간
            int checked = 0;
            for(int time : times) {
                // 총 시간/각 심사관의 심사시관 = 해당 시간 동안 심사하는 사람의 수
                // 즉, 총 걸리는 시간 동안 
                // 각 심사관이 심사하는 사람의 수를 합했을 때 
                // 'n'이 되는 최소 시간을 찾는 것이 목표
                checked += mid/time;
                if(checked >= n){
                    minVal = mid;
                    R = mid - 1;
                    break;
                }   
            }
            if(checked < n){
                L = mid + 1;
            }
        }
        return minVal;
    }
    
}