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

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

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

2021-08-30

---

 static long solution(int n, int[] times) {
        long answer = 0;
        Arrays.sort(times);
        long left = 1;
        long right = n * (long) times[times.length - 1];
 
        while(left <= right) {
            long mid = (left + right) >> 1;
            long cnt = 0;
            for (int time : times) {
                cnt += (mid / time);
            }
 
            if(cnt >= n) {
                right = mid - 1;
                answer = mid;
            }
            else left = mid + 1;
        }
        return answer;
}

#문제풀이

이분탐색 문제.

 

1) left는 1로 잡고, right는 가장 최악인 n * (long) times[times.length - 1] 로 잡는다.

 

2) left와 right의 mid 값을 구한 후, 해당 mid값 기준으로 몇 명을 심사대에서 통과 시킬 수 있는지 계산한다.

 

3) 만약 cnt가 n보다 크거나 같은 경우는 기준 값을 줄일 수 있는 경우이므로, right을 mid-1로 땡겨준다.

 

4) 만약 cnt가 n보다 작은 경우는 기준 값이 부족한 경우이므로, left를 mid + 1로 옮겨준다.

 

5) left <= right까지 2~4를 반복한다.