Programmers - 입국 심사 with JAVA (V)

 

문제

심사관들이 각각 한명을 심사하는데 걸리는 시간들이 주어지고 대기자 명수가 주어진다. 모든 사람을 검사하는데 걸리는 가장 짧은 시간은??

 

 

 

로직

기본적으로 대기자수의 범위가 너무 크기때문에 자료구조를 활용하는 등의 방법은 시간 초과의 문제가 있다. 따라서 이분탐색을 사용한다.

 

1. s_time : 총 검사 시간의 최소값 - 1

2. e_time : 총 검사 시간의 최대값 - 배열의 가장 큰 수 * 사람 수

3. 이분 탐색 시작 (의미 : 해당 시간만큼 검사를 진행한다면 몇명을 검사할 수 있는지 확인)

-> 해당 시간만큼 검사시 검사해야하는 사람을 모두 검사하지 못한다면 ? s_time = n_time + 1;

-> 해당 시간만큼 검사시 검사해야하는 사람을 모두 검사한다면? e_time = n_time - 1;

 

 

추가적으로, 사람수(count)를 측정할때, 사람 수의 범위는 int로 처리 불가능하므로 long처리를 해주어야 한다.

(e_time의 최댓값 : 10억*10억 -> m_time의 최댓값 : 10억*5억 -> time의 최솟값 : 1이므로) => 아래 코드 참조

 

 

 

코드

import java.util.*;
public class Solution {
    public static long solution(long n, int[] times) {
        Arrays.sort(times);
        long s_time = 1;
        long e_time = n*times[times.length-1];
        long answer = n*times[times.length-1];
        while(s_time <= e_time){
            long m_time = (s_time+e_time)/2;
            long count = 0;
            for(int time : times){
                count += m_time/time;
            }
            if(count < n){
                s_time = m_time+1;
            }
            else{
                answer = Math.min(answer, m_time);
                e_time = m_time-1;
            }
        }
        return answer;
    }
}