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

 

문제

입국심사를 기다리는 사람들과 심사를 맡은 심사관들이 있다. 

심사를 기다리는 사람 수를 n, 각각의 심사관이 1명을 심사하는 데 걸리는 시간이 담긴 배열 times가 주어졋을 때

n명 모두 심사를 받기 위해서 걸리는 최소 시간을 리턴하는 문제이다.

 

- 1 <= n <= 10억(명)

- 1분 <= times 요소 <= 10억(분)

- 1 <= times 배열 길이 <= 10만(명)

 

1) 브루트 포스 => 정확도 33.3% 시간초과

처음엔 단순하게 주어진 논리대로 구현했다.

- while문을 돌면서 시간을 1씩 증가시킨다.

- 'int time(심사하는 데 걸리는 시간)', 'int inspected(현재 심사중인 사람 소요시간)' 속성을 담는 Examiner(검사관)클래스를 두었다.

- ArrayList<Examiner> Immigration 을 생성하고, 시간이 1 지날 때마다 inspected를 1씩 증가한다.

- 만약 inspected가 time과 같아지면 complete(완료된 사람)을 하나 증가시키고 해당 인스턴스의 inspected변수를 0으로 초기화한다.

- n에서 완료된 사람을 뺄셈연산하고 n이 0이되는 시간을 리턴한다.

 

하지만 10억명의 사람을 검사하고, 심사관이 10만명으로 주어진 경우에

시간이 1 증가할 때마다 ArrayList를 10만번씩 선형탐색하고, 10억명의 complete가 나올 때까지 반복해야 하기 때문에 효율적이지 못하다.

 

 

2) 이진탐색 => 정확도 100%

문제의 요구사항은 단순히 '최소시간'을 리턴하는 것이다.

따라서 탐색 대상을 '모든 사람이 검사 받는 시간'으로 두고 이진탐색으로 시간을 추정해나갈 수 있다.

- 최소 검사시간 : 1

- 최대 검사시간 : 검사받는 사람 수 * 제일 적은 검사관의 시간

- 시간을 추정해서 해당 시간동안 n명을 검사할 수 있는지를 체크하면 된다. 

- (ex) n = 6, 20 min ? times = {7,10} : 20 / 7 + 20 / 10 = 2 + 2 => 4명 검사 가능 (조건만족x)

- (ex) n = 6 30 min ? times = {7,10} : 30 / 7 + 30 / 10 = 4 + 3 => 7명 검사 가능 (조건만족o)

 

 

코드

import java.util.ArrayList;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        int n = 6;
        int[] times = {7, 10};
//        System.out.println(solution1(n, times)); // 1) 브루트포스 : 시간초과
        System.out.println(solution2(n, times)); // 2) 이진탐색 : 성공
    }


// solution1 
    static class Examiner {
        int time;
        int inspected;

        public Examiner(int time) {
            this.time = time;
            this.inspected = 0;
        }
    }

    static int setInspectedTime(ArrayList<Examiner> immigration) {
        int complete = 0;

        for (int i = 0; i < immigration.size(); i++) {
            Examiner e = immigration.get(i);
            e.inspected++;
            if (e.time == e.inspected) {
                complete++;
                e.inspected = 0;
            }
        }

        return complete;
    }

    static long solution1(int n, int[] times) {
        long current_time = 0;

        Arrays.sort(times);
        ArrayList<Examiner> immigration = new ArrayList<>();
        for (int i = 0; i < times.length; i++) {
            immigration.add(new Examiner(times[i]));
        }

        int wait = n;
        while (wait > 0) { // 등호?
            int complete = setInspectedTime(immigration);
            wait -= complete;
            current_time++;
        }

        return current_time;
    } // solution1 end

    // 2) 이진탐색
    static long solution2(int n, int[] times) {
        Arrays.sort(times);
        long shortest = 1, longest = (long) n * times[0]; 

        long result = Long.MAX_VALUE;
        while (shortest <= longest) {
            long mid = (shortest + longest) / 2;
            if (isPossible(mid, times, n)) {
                result = Math.min(mid, result);
                longest = mid - 1;
            } else {
                shortest = mid + 1;
            }
        }

        return result;
    }

    // 추정한 시간(time) 내에 사람 n명을 검사할 수 있는지 확인
    static boolean isPossible(long time, int[] times, int n) {
        long cnt = 0;
        for (int i = 0; i < times.length; i++) {
            cnt += time / times[i];
        }
        return cnt >= n;
    }
}

 

 

채점결과