[Programmers] 입국심사(이분탐색) - JAVA

1. 문제

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

프로그래머스

 

2. 풀이과정

이분 탐색 문제인 걸 알면서 풀었는데도, 아이디어가 잘 떠오르지 않은 문제였다.

이분 탐색 문제를 많이 풀어봐야겠다..!

 

사람수 n명이 주어지고,  입국심사관이 한 명을 심사하는데 걸리는 시간이 times 배열로 주어진다.

모든 사람들이 입국심사를 가장 빨리 끝내는 시간을 구하는 문제이다.

 

문제접근

이 문제는 최악의 경우 n = 1,000,000,000 이고, 각 심사관이 한명을 검사하는 시간이 1,000,000,000 이다.

또한, 심사관은 최대 100,000명이 될 수 있다. => 시간 초과에 유의해야 한다.

 

이분탐색으로 접근해서 풀어야 시간 초과가 발생하지 않으면서 문제를 해결할 수 있다.

 

1. times 배열 오름차순 정렬
2. 이분 탐색 범위 지정
   1. left = 0(최소 시간)
   2. right = 최대 시간 x 사람 수(최대 시간)
3. 이분 탐색 시작(right >= left)
   1. mid(제한된 시간) 구한다 
   2. times를 돌면서 mid(제환된 시간)에서 times[i] 로 나눈 몫을 count에 누적한다. => 제한된 시간동안 몇 명을 처리할 수 있는지 계산
   3. count >= n이면, 제한된 시간에 모든 사람이 검사받을 수 있다.
      1. 제한된 시간 answer에 저장(정답 후보)
      2. 최솟값을 구하기 더 짧은 시간을 탐색(right = mid - 1)
   4. count < n이면, 제한된 시간안에 모든 사람이 검사받을 수 없다.
      1. 더 긴 시간이 필요(left = mid + 1)
4. answer(결과) 반환

 

3. 코드

class Solution {
    public long solution(int n, int[] times) {
        Arrays.sort(times);
        
        long left = 0;
        long right = times[times.length - 1] * (long) n;
        
        long answer = 0;
        
        while (right >= left) {
            long mid = (left + right) / 2;
            
            long count = 0;
            for(int i = 0; i < times.length; i++) {
                count += (mid / times[i]);
            }
            
            if(count >= n) {
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
  
        return answer;
    }
}