문제

[프로그래머스] 입국심사
https://school.programmers.co.kr/learn/courses/30/lessons/43238

풀이

조건

• 처음에 모든 심사대는 비어있습니다.
• 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다.
• 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
• 모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.
• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

풀이 순서

• 총 걸리는 시간을 기준으로 이진 탐색을 한다.
• 정한 시간을 이용하면 총 몇 명을 심사할 수 있는지 확인하고 그에 따른 결과로 이진 탐색할 범위를 정한다.
  • 정한 시간으로 목표 인원(n)보다 더 적게 처리한다면 시간이 더 필요하다는 뜻이다.
    • left = mid + 1
  • 정한 시간으로 목표 인원(n)보다 더 많게 처리하거나 딱 맞게 처리할 수 있다면 시간을 더 줄여도 된다는 뜻이다.
    • right = mid - 1
    • 딱 맞게 처리할 수 있는 상황 중에서도 최소값을 구해야 하기 때문에 딱 맞는 경우도 이 조건에 포함시켜야 한다.

코드

Java

import java.util.*;

public long solution(int n, int[] times) {
		long answer = 0;

		Arrays.sort(times); // 심사관 별 걸리는 시간 정렬

		long left = 0;
		long right = times[times.length - 1] * (long) n; // 모든 심사를 끝내는 데 가장 오래 걸리는 시간

		while (left <= right) {
			long mid = (left + right) / 2; // 현재 확인할 모든 심사를 끝내는 시간
			long sum = 0; // 몇 명 처리할 수 있는지 저장할 배열

			// 현재 총 걸리는 시간을 각 심사위원이 걸리는 시간으로 나눠서 몇 명 심사할 수 있는지 구하기
			for (int i = 0; i < times.length; i++) {
				sum += mid / times[i];
			}
			
			// 현재 시간으로는 목표 인원보다 더 적게 처리 -> 시간 더 필요
			if (sum < n) {
				left = mid + 1;
			} 
			// 현재 시간으로는 목표 인원보다 더 많게 처리하거나 딱 맞게 처리 가능 -> 시간 더 줄여도 됨
			else {
				right = mid - 1;
				answer = mid;
			}
		}

		return answer;
	}

정리

• 이진 탐색을 오랜만에 풀어서 구현하는 데 시간이 오래 걸렸다.
• 총 걸리는 시간을 이용해 이진 탐색을 하는 방법을 알았다.