글 쓰는 시간

이분탐색

이분탐색 자체는 리트코드 35.Search Insert Position을 통해서 처음 접했고,

프로그래머스에서는 입국심사를 통해 처음 접했다.

리트코드 문제에서 이분탐색이라는 개념을 이해했고 프로그래머스 문제에서 사고를 확장하는데 도움이 됐다.

풀이

프로그래머스 입국심사 문제 풀이

1. times 배열을 오름차순으로 정렬한다.
2. 최소시간 min은 최단 수행시간인 times[0] 만에 모든 입국심사가 끝났을때이다.
3. 최대시간 max는 최장 수행시간인 times[times.length] 로 n명을 입국심사 한 값이다.
4. min 과 max 사이에서 이분탐색을 수행한다.
5. 중간값 mid 의 시간동안 각각의 심사관이 처리할 수 있는 인원 수 sum을 각각 더한다.
6. sum == n 이 되는 mid의 최소값을 구한다.

최종 코드

import java.util.*;
class ImmigrationInspection {
    public long solution(int n, int[] times) {
    	// times 를 오름차순으로 정렬
        Arrays.sort(times);
        long answer = 0;
        
        // 최소값, 최대값 설정
        long min = (long)times[0];
        long max = (long)times[times.length -1] * n;
        long mid = 0;
        
        // 이분탐색 수행
        while (min <= max) {
            long sum = 0;
            mid = (min + max) /2;
            
            // 중간값 mid 의 시간동안 각각의 심사관이 처리할 수 있는 인원 수
            for (int time : times) {
                sum += mid / time;
            }
            
            // sum == n 을 만족하는 mid 의 최소값을 구한다.
            if (sum >= n) {
                answer = mid;
                max = mid -1;
            } else {
                min = mid +1;
            }
        }
        return answer;
    }
}