[PG] 입국심사 JAVA

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

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

입국심사를 받아야 하는 사람 수 int n, 심사관 별 심사 소요시간 int[] times 가 주어진다.

모든 사람이 입국심사를 마치기까지 걸리는 최소시간을 반환해야한다.

 

1. 한 심사대에서는 동시에 한 명만 심사를 할 수 있다.

2. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

 

 

 

풀이 .

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        Arrays.sort(times);

        long answer = (long)times[times.length - 1] * n;  // 최악의 경우 : n명 모두 최대시간으로 검사
        long max = (long)times[times.length - 1] * n;  // 최악의 경우 : n명 모두 최대시간으로 검사
        long min = 1;  // 최고의 경우 : 1초만에 모든 검사 끝

        while(min <= max) {  // 시간 범위를 점점 좁히다가 엇길리게 되면 답을 찾은 것임
            long mid = (min + max) / 2;

            long sum = 0;
            for(int time : times) {  // 각 심사관별로 mid 시간동안 몇 명을 검사할 수 있는지의 총합
                sum += mid / time;
            }

            if(sum >= n) {
                answer = Math.min(answer, mid);
                max = mid - 1;  // n명 이상 해결이 가능하다 -> 시간을 줄인다
            }else {
                min = mid + 1;  // n명까지 해결하지 못한다 -> 시간을 늘린다
            }
        }

        return answer;
    }
}

 

비슷한 풀이법을 떠올리지조차 못했다. 구글링을 통해 다른이의 코드를 이해만 하고 넘어간 수준이다.

 

문제를 처음 봤을 때 했던 생각은..

 

그냥 단순하게 시간을 나타내는 변수를 두고 반복을 돌리면서,

각 심사관들이 다음 심사를 하려면 시간이 얼마나 지나야 하는가를 계산해서,

사람들을 어느 심사관에게 배치할 것인지를 고르려고 했다.

 

막상 곧이곧대로 구현해보려니 쉽지도 않았고 완성했어도 시간초과가 났을 거다.

(이분탐색이라고 분류가 돼있는데도 이런 방법 밖에 생각하지 못했다.)

 

n과 times[]의 최대 원소의 최대값이 10억인 걸 보고 이분탐색, DP 등 시간을 아낄 수 있는 방식을 떠올릴 수 있어야 한다.

(완전탐색은 택도 없이 시간초과)

 

1. 엄청나게 큰 n을 보고 이분탐색을 떠올린다

2. 심사에 걸리는 시간을 반환하는 것 -> 시간을 조정해가며 심사관들이 해당 시간 내에 몇명이나 심사할 수 있는지 확인

3. 이분 탐색을 통해 시간을 절반씩 줄여나간다.

 

아마 for each 부분을 생각 해내는 게 핵심이지 않았을까 싶다. (주어진 시간 내에 모든 심사관이 계속해서 심사를 이어간다면 몇 명의 심사를 마칠 수 있는지)

 

 

 

너무 어렵다.

객관적으로 그렇게까지 어려운 문제는 아닌 거 같은데 그냥 나한테는 어려운 거 같아서 더 짜증난다.