문제 출처

코딩테스트 연습 > 이분탐색 > 입국심사
https://school.programmers.co.kr/learn/courses/30/lessons/43238

문제 설명

입국 심사 기다리는 인원 수 n, 심사관이 한 명 심사하는데 걸리는 시간 배열 times가 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간 최솟값 return 하라.

% 한 심사대에 한 명씩 심사, 빨리 끝나는 심사대가 있다면 기다린 후에 그곳에서 심사 받을 수 있다.

접근 방법

이분탐색 풀이 문제로 가장 짧게 걸리는 시간 left, 가장 길게 걸리는 시간 right를 설정하고, left > right가 될 때까지 mid(정답)을 유추한다.

mid를 설정하고, mid 시간 동안 심사관이 심사할 수 있는 인원을 전부 더하고,
만약 그 수가 총 심사해야하는 인원인 n보다 크거나 같으면 right를 mid -1로 지정(총 심사 인원보다 더 많이 탐지하므로 시간을 감소).
그 수가 총 심사해야하는 인원인 n보다 작으면 left를 mid+1로 설정한다(총 심사 인원보다 더 적게 탐지하므로 시간을 증가).

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        
        Arrays.sort(times);
        
        long left = 1;
        long right = (long) times[times.length-1]*n;
        
        // left > right 될 때까지 mid(정답 유츄) 탐지
        while(left <= right){
            long mid = (left + right)/2;
            long fin = 0;
            for(int time : times){
                fin += mid/time;
                if(fin >= n) break;
            }
            if(fin >= n) {
                answer = mid;
                right = mid-1;
            }
            else left = mid +1;
        }
        return answer;
    }
}

Review

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        // 오름차순 정렬
        Arrays.sort(times);
        // high 는 times에서 가장 큰 값 * n(가장 오래 걸림을 가정), low 는 1로 설정
        long high = (long) times[times.length - 1]*n;
        long low = 1;
        
        while(low <= high){
            long mid = (low + high) / 2;
            long count = 0;
            // mid 시간 동안 심사관들이 얼마나 해결할 수 있나 확인
            for(long time : times){
                count += mid/time;
            }
            
            if(count >= n){
                answer = mid;
                high = mid -1;
            } else low = mid +1;
        }
        
        return answer;
    }
}

알게된 점

문제에선 "시간"을 바탕으로 이분탐색을 진행해야한다. 최소의 시간을 구하는 문제이므로 시간의 정답을 mid로 설정하고, 그 mid의 범위를 절반씩 줄여나가는 방향으로 접근한다.

처음 풀었던 풀이는 가장 짧게 걸리는 심사원과 가장 길게 걸리는 심사원의 결과를 비교하면서 진행했다.(당연히 틀렸다.)

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        
        Arrays.sort(times);
        
        int low = 1;
        int high = (n/times.length)*2;
        
        int low_result = 0;
        int high_result = 0;
        
        int low_value = times[0];
        int high_value = times[times.length-1];
        
        //
        while(low < high){
            if(low_result < high_result){
                low_result+=low_value;
                low++;
            }
            else if(low_result > high_result){
                high_result += high_value;
                    high--;
            }
            else{
                low++;
                high--;
                low_result+=low_value;
                high_result+=high_value;
            }
            
            if(low >high){
                return (long) Math.max(low_result, high_result);
            }else{
                return (long) low_result+low_value;
            }
        }
        return answer;
    }
}

문제푼 흔적

아이패드로 풀어보았다.



Review