[Programmers] 입국심사

난이도 : Level 3

문제링크

• 입국심사를 위해 n명이 줄을 서있습니다.
  • 가장 앞에 서있는 사람은 비어있는 심사대로 가서 심사를 받을 수 있습니다.
  • 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
• 각 입국심사관이 심사하는데 걸리는 시간이 주어집니다.
  • 입국심사관은 동시에 한명만 심사할 수 있습니다.
• 모든 사람이 심사를 받는데 걸리는 최소 시간을 리턴하세요.

 

해설

1. 심사에 걸리는 모든 시간을 대상으로 이분탐색

public long solution(int n, int[] times) {
    Arrays.sort(times);
    int count = 0;
    long minTime = 1, midTime = 0, maxTime = (long)times[0] * n;

    while (minTime <= maxTime) {
        midTime = (minTime + maxTime)/2;
        count = immigration(times, midTime, n);
        if (count == n) {
            maxTime = midTime-1;
        } else {
            minTime = midTime+1;
        }
    }

    return minTime;
}

• 심사에 걸리는 최소시간을 minTime 변수에 할당한다.
• 가장 빨리 걸리는 시간부터 오래걸리는 시간을 투포인터로 두고 이분탐색하면서, midTime 시간으로 n명의 심사가 가능한지 확인한다
  • 심사하는데 충분한 시간이라면 더 적은시간으로 심사할 수 있는지 확인하기 위해 왼쪽 영역을 다음 반복의 범위로 설정한다.
    • maxTime을 midTime-1로 줄인다.
  • 심사하는데 부족한 시간이라면 시간을 늘리기 위해 오른쪽 영역을 다음 반복의 범위로 설정한다.
    • minTime을 midTime+1로 늘린다.
• minTime을 리턴한다.

 

2. 주어진 시간으로 심사할 수 있는 인원 구하기

private int immigration(int[] times, long time, int n) {
    int count = 0;
    for (int i = 0; i < times.length; i++) {
        count += time / times[i];
        if (count >= n) return n;
    }
    return count;
}

• 심사위원관별 걸리는 시간을 전체 시간으로 나누었을 때의 몫을 누적합한다.
• 누적합이 심사할 수 있는 사람수이다. 

 

 

 

블로그 참고

• 갈대상자 - [Java] 입국 심사