[프로그래머스] 이분탐색 - 입국심사

https://syundev.tistory.com/170

참고하여 문제를 해결하였다.

 

 

문제를 읽고 왜 이게 이분탐색이지..? 생각했다.

아무리 이분 탐색으로 해결하려고 고민해도.. 각이 안 나와서 결국 서칭..

 

나는 문제를 매 시점마다 처리하는 것으로 해결하려는 경향이 있다.

하지만 이러한 풀이법은 비효율적인 계산이 많다..

역시나 이 문제도 시점마다 처리하는 것이 아닌 입국심사가 가능한 시간 중 가장 효율적인 시간을 찾는 것이었다.

이 때 사용한 개념이 이분 탐색이었다.

 

입국 심사가 가능한 시간 중 가장 효율적인 시간을 찾는 방법

해당 시간 안에 심사대마다 심사할 수 있는 사람의 수를 더해주어 n과 비교해준다.

이때 입국 심사가 가능한 시간은 가장 적은 시간부터 긴 시간으로 나열되어있기 때문에

이분 탐색을 사용할 수 있고, 기다리는 사람이 매우 많을 수 있기 때문에 이분 탐색을 사용하는 것이 가장 효율적이다.

 

import java.util.*;
class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
         Arrays.sort(times);
        long left=0;
        long right=(long)times[times.length-1]*n;
        
        while(left <= right) {
        	long mid=(left+right)/2;
        	long count=0; //x시간동안 입국 가능한 사람 수
        	for(int i=0;i<times.length;i++) {
        		count += (long)mid/times[i];
        	}
        	if(count>=n) {
        		right=mid-1;
        		answer=mid;
        	}
        	else {
        		left=mid+1;
        	}
        }
        return answer;
    }
}