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

문제출처

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

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

 

문제풀이

이분탐색을 응용한 문제입니다. 처음에 왜 이문제가 이분탐색인지 몰랐는데 다른 블로그를 보면서 이해할 수 있었습니다. 이 문제는 times배열에 각 심사관이 한명을 심사하는데 걸리는 시간 정보가 주어지고 n명을 모두 심사할 때 심사시간의 최소값을 구하는 문제입니다.

 

n의 최대값은 10억이며 times의 최대 크기는 10만입니다. n의 값이 크기 때문에 일반적인 풀이로는 풀수 없고 시간복잡도를 줄일 수 있는 답안을 생각해야 합니다.

 

입출력 예시로 주어진 대로 6명을 심사하고 각각 7분, 10분이 걸리는 2명의 심사관이 있는 경우를 생각해보겠습니다.

걸리는 시간을 기준으로 이분탐색을 할 예정이며 최소시간은 1분 최대시간은 n X 가장 오래걸리는 심사관의 시간 으로 시작했습니다. 이 문제에서 이분탐색을 할 때 핵심은 mid시간 이내에 심사가능한 인원의 수는 sum(mid / times[i])라는 것입니다.

 

최소시간을 left, 최대시간을 right변수에 담아 평균 시간을 mid에 저장합니다. 즉 1 // 30 // 60 으로 이분탐색을 시작합니다.

mid = 30

30분 이내에 심사가능한 인원은 (30 / 7) + (30 / 10) 으로  4 + 3 = 7명입니다.

7은 6보다 크므로 6명을 심사하기 위해서는 30분보다 더 적은 시간에도 가능한 것을 유추할 수 있습니다. 즉 rigth 변수값을 mid - 1을 해 29로 저장한뒤 재탐색 합니다. 이때 29분에는 6명을 심사할 수 없을 수도 있기 때문에 answer에 mid값을 저장합니다.

 

mid = (1 + 29) / 2 = 15

1 // 30 // 60 에서 1 // 15 // 30 으로 탐색범위가 반으로 줄었습니다. 15분 이내에 심사가능한 인원은 (15 / 7) + (15 / 10) = 2 + 1 = 3명입니다. 3은 6보다 작으므로 6명을 심사하기 위해서는 15분보다는 더 시간이 필요한 것을 알 수 있습니다. 이분탐색을 위해 left 값을 1에서 16으로 바꾼 후 탐색을 다시 시작합니다.

 

mid = (16 + 30) / 2 = 22

1 // 15 // 30 에서 16 // 22 // 30 으로 탐색범위가 또 반으로 줄었습니다. 22분 이내에 심사가능한 인원은 (22 / 7) + (22 / 10) = 3 + 2 = 5명입니다. 5는 6보다 작으므로 6명을 심사하기 위해서는 22분보다 시간이 더 필요합니다. left 값을 16에서 23으로 바꾼 뒤 탐색을 다시 시작합니다.

 

반복해서 나아가면

mid = (23 + 30) / 2 = 26

....

 

mid =  (26 + 30) / 2 = 28

(28 / 7) + (28 / 10) = 4 + 2 = 6명이므로 28이 정답임을 알 수 있습니다.

 

각각의 탐색과정에서 범위가 반으로 줄고 있으므로 시간복잡도는 O(logN)입니다.

 

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EC%9E%85%EA%B5%AD%EC%8B%AC%EC%82%AC.java

sw93/algorithm

 

import java.util.Arrays;
class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        Arrays.sort(times);
        
        long left = 1;
        long right = (long)n * times[times.length - 1];
        while (left <= right) {
            long mid = (left + right) / 2;
            long count = 0;
            
            // 심사 가능한 인원 = 시간 / 심사하는데 걸리는 시간
            for (int i=0; i<times.length; i++) {
                count += mid / times[i];
            }
            
            // mid 시간동안 심사한 인원이 n명보다 적은 경우 시간이 더 필요
            if (count < n) {
                left = mid + 1;
            } else { // 심사한 인원이 n명 이상인 경우 시간을 줄여도 됨
                right = mid - 1;
                answer = mid;
            }
        }
        
        return answer;
    }
}