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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43238

프로그래머스

 

---

 

문제 개요

이 문제는 여러 심사대를 통해 주어진 사람 수 n명을 가능한 한 최소 시간에 모두 심사하는 방법을 찾는 문제입니다. 각 심사대의 심사 시간은 다르며, 모든 사람이 심사를 완료하는데 걸리는 시간의 최솟값을 구해야 합니다.

문제 접근 방식

입국 심사 문제는 이분 탐색을 활용해 최적의 답을 찾아낼 수 있습니다. 이 문제를 해결하기 위해 전체 시간을 이분 탐색으로 줄여가며 필요한 최소 시간을 찾아낼 수 있습니다.

문제 풀이

1. 이분 탐색 설정:
   • 가능한 시간 범위를 최소값 left = 0에서 시작하고, 최대값 right = 가장 오래 걸리는 심사관의 시간 * 사람 수로 설정합니다.
   • 이 값은 모든 사람을 한 명의 심사관이 최대로 심사하는 경우의 시간을 고려해, 이분 탐색의 범위를 설정하는 방식입니다.
   • 이분 탐색
2. 중간 값으로 검증:
   • mid를 left와 right의 중간값으로 설정하고, 이 시간 내에 심사할 수 있는 총 인원 수를 구합니다.
   • 각 심사관이 mid 시간 동안 처리할 수 있는 사람 수는 mid / times[i]로 계산합니다.
   • 모든 심사관에 대해 이 값을 합산해 총 심사 가능한 인원 수 sum을 구합니다.
3. 조건에 따라 탐색 범위 조정:
   • sum >= n인 경우, mid 시간이 충분하거나 넘치므로 시간을 줄이기 위해 right = mid - 1로 범위를 줄입니다.
   • 반대로, sum < n인 경우, 시간이 부족하므로 left = mid + 1로 범위를 늘립니다.
4. 최솟값 갱신:
   • 조건을 만족할 때마다 answer 값을 갱신해 최종적으로 가장 작은 시간을 찾습니다.

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        
        // 이분 탐색의 시작(left)과 끝(right) 설정
        long left = 0;
        long right = times[times.length - 1] * (long)n;
        
        while(left <= right) {
            long mid = (right + left) / 2;
            long sum = 0;

            // 각 심사관이 mid 시간 동안 처리할 수 있는 인원 계산
            for(int i = 0; i < times.length; i++) {
                sum += mid / times[i];
            }

            // 조건에 따라 탐색 범위 조정
            if(sum >= n) {
                right = mid - 1;
                answer = mid; // 조건을 만족하면 answer 갱신
            } else {                
                left = mid + 1;
            }
        }
        
        return answer;
    }
}