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

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

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

[ 풀이 ]

먼저 이 문제는 이분탐색 알고리즘을 이용해 풀었다. 왜 이분탐색 알고리즘을 이용해야 하는지 처음에는 이해가 되지 않아서 구글링을 통해 힌트를 얻을 수 있었다.

핵심은 바로 " 총 심사시간( 추정 ) / 각 심사관이 심사를 하는 데 걸리는 시간 = 각 심사관이 심사를 완료하는 입국심사자 수 " 라는 것이다. 각 심사관이 심사를 완료하는 입국 심사자 수를 모두 더하면 심사가 완료된 총 입국 심사자수가 된다. ( 편의상 sum 이라고 한다 )

 

1. sum이 목표로 하는 입국 심사자 수 n 보다 값이 작을 경우 모든 입국심사자가 심사가 완료되지 않았다는 뜻이고 즉, 추정했던 총 심사시간이 실제 총 심사시간 보다 작다는 뜻이된다.

2. sum이 목표로 하는 입국 심사자 수 n 보다 크거나 같을 경우 모든 입국심사자가 심사가 충분히 완료되었다는 뜻이다.

 

이를 이용해 위 조건을 따져가면서 총 걸리는 입국심시시간을 추정할 수 있다.

 

이분 탐색을 위해

탐색 시작 위치를 1초라고 두고,

 

탐색 끝 위치를 times[times.length - 1] * n; 라고 둘 수 있다.( 탐색 끝 위치 : 시간이 최대로 걸리는 최악의 경우이다. 입국심사자가 빈 자리를 거르고 가장 시간이 오래걸리는 심사관 자리로만 가는 경우이다. 이를 위해서 미리 times[] 배열을 오름차순으로 정렬하였다.)

 

중간값 mid는 시작 위치와 끝 위치를 더한 후 2로 나눈 값이 된다.

[ 전체 코드 ] 

import java.util.*;
class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        Arrays.sort( times );
        long start = 1;
        long end = (long)times[times.length - 1] * n; 
        long mid = 0;
        
        while( start <= end ){
            mid = ( start + end ) / 2; // 총 추정시간( 모든 사람이 심사를 받는데 걸리는 시간 )
            long sum = 0;
            for( int time : times ){                
                sum += mid / time; 
                // ( mid / time ) >> 각 심사관이 맡을 수 있는 입국심사자 수
                // 즉 sum 은 심사관들이 심사를 완료한 입국심사자의 총 수가 된다.
            }
            
            // 심사관이 모든 입국심사자수를 검사하지 못했다는 뜻. 즉 추정시간이 더 오래 걸려야 한다.
            if( sum < n ){  
                start = mid + 1;
            } else {
                end = mid - 1 ;
                answer = mid;
            }            
        }        
        return answer;
    }
}