프로그래머스 3단계 : 입국심사 (Java 자바)

문제 설명

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항
입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
심사관은 1명 이상 100,000명 이하입니다.

 

 

제한사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

 

입출력 예

 

 

풀이

n명의 사람들이 입국심사를 받는데 걸리는 최소 시간을 구하는 문제입니다. 이분 탐색을 사용하여 최소 시간을 효율적으로 찾아낼 수 있도록 하였습니다.

Arrays.sort(times);: 주어진 심사 시간을 오름차순으로 정렬합니다. 이렇게 정렬하면 가장 빨리 끝나는 심사대부터 사용할 수 있게 됩니다.

long left=0;과 long right=(long)times[times.length-1]*n;: 초기에 이분 탐색을 위한 left와 right 값을 설정합니다. left는 0부터 시작하고, right는 가장 긴 심사 시간(times 배열의 가장 큰 값)과 n을 곱한 값으로 설정합니다. 이 범위 내에서 최소 시간을 찾아야 합니다.

while(true) { ... }: 무한 루프를 돌면서 이분 탐색을 수행합니다.

long mid=(left+right)/2;: 현재 left와 right 사이의 중간 값을 계산합니다.

long sum=0;과 for(int data:times) { sum+=(mid/data); }: 현재 중간값(mid)을 사용하여 각 심사대에서 몇 명을 심사할 수 있는지를 계산하고 합산합니다. 이를 통해 mid 시간 동안 처리할 수 있는 총 인원 수를 구합니다.

if(sum<n) { left=mid+1; }: 계산한 총 인원 수(sum)가 목표 인원(n)보다 작다면, 시간을 늘려서 더 많은 인원을 심사할 수 있도록 합니다. 이분 탐색의 특성상 left 값을 증가시켜 범위를 오른쪽으로 좁힙니다.

else { right=mid-1; answer=mid; }: 계산한 총 인원 수(sum)가 목표 인원(n) 이상이라면, 시간을 줄여서 더 적은 인원을 심사하도록 합니다. answer에 mid 값을 저장하고, 이 값이 최소 시간이 됩니다. 이분 탐색의 특성상 right 값을 감소시켜 범위를 왼쪽으로 좁힙니다.

return answer;: 최소 시간인 answer 값을 반환합니다.

 

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        
        // 심사 시간을 오름차순으로 정렬
        Arrays.sort(times);
        
        // 이분 탐색을 위한 범위 설정
        long left = 0;
        long right = (long) times[times.length - 1] * n;

        // 이분 탐색 시작
        while (true) {
            if (left > right) {
                break; // 범위를 벗어나면 종료
            }
            long mid = (left + right) / 2; // 중간값 계산
            long sum = 0; // 현재 시간(mid)동안 처리한 인원 수

            // 각 심사대에서 처리한 인원 수 합산
            for (int data : times) {
                sum += (mid / data);
            }

            // 처리한 인원 수가 목표 인원(n)보다 작다면 시간을 늘려 범위를 오른쪽으로 좁힘
            if (sum < n) {
                left = mid + 1;
            } else {
                // 처리한 인원 수가 목표 인원(n) 이상이라면 시간을 줄여 범위를 왼쪽으로 좁힘
                right = mid - 1;
                answer = mid; // 최소 시간을 갱신
            }
        }

        return answer; // 최소 시간 반환
    }
}