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

👨‍✈️ 입국심사 

 

이분 탐색을 하라는데 뭘 이분 탐색해야 하는지 모르겠어서;; 

한참을 고민하다가 결국 구글링을 했는데,

시간을 이분 탐색해야 하는 것이었다. 

 

시간은 1부터 연속적으로 흘러가야 한다는 생각에 갇혀서 

시간을 이분 탐색한다는 생각 자체를 못했다 . .

 

---

문제 설명

 

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

 

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

 

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

 

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

입출력 예

 

n	times	return
6	[7,10]	28

 

---

🔑 IDEA

Binary Search는 분할 정복 기법(Divide and Conquer)을 응용한 것으로, 

반으로 나누어 가면서 목표하는 값을 찾아나가는 방법이다. 

절반씩 나누어 탐색하기 때문에 시간복잡도가 O(logN)이다. 

따라서 이 문제와 같이 input값이 매우 큰 경우에 이진 탐색을 이용하면 효율적으로 문제를 해결할 수 있다.

 

이진 탐색을 이용하여 찾을 값은 바로  "모든 사람이 심사를 받는데 걸리는 시간의 최솟값" 이다. 

 

모든 사람이 심사를 받는데 걸리는 시간이 가장 긴 경우는

"가장 오래걸리는 심사관에게 모든 사람이 심사를 받는 경우"이다.

우리가 찾고자 하는 값은 이 값보다는 작을 것이다. 

 

또한, 우리가 찾고자 하는 값은

가장 적게걸리는 심사관이 한 명을 심사하는데 걸리는 시간보다는 클 것이다. 

 

즉,  times[]를 오름차순 정렬했을 때 우리가 찾고자 하는 값은 

[times[0], times[times.length-1] * n] 범위에 있다는 것이다. 

 

예를 들어, 테스트케이스에서 n이 6이고 times가 [7, 10] 인 경우에

우리가 찾고자 하는 값은 7과 60 사이에 있으므로 [7, 60]을 이진 탐색하면 된다. 

 

💡  나의 풀이

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        Arrays.sort(times);
        
        long answer = Long.MAX_VALUE;
        long start = times[0];
        long end = (long)times[times.length-1] * n;
        
        while(start <= end) {
            long done = 0;
            long mid = (start + end) / 2;
            
            for(int time: times) {
                done += mid / time;
            }
            
            if(done >= n) {
                answer = mid;
                end = mid-1;
            }
            else start = mid+1;
        }
        
        return answer;
    }
}

 

 

---

 

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