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

📚 문제 설명

📌 입국심사

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

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

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

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

제한사항

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

🔎 입출력 예

💻 코드

// 한 심사대에는 동시에 한 명만
// 가장 앞에 있는 사람은 비어 있는 심사대 or 더 빨리 끝나는 심사대가 있으면 기다렸다 심사
// 걸리는 시간 최소
import java.util.*;
class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        
        Arrays.sort(times);
        long max = (long) times[times.length-1] * n; // 최악의 시간
        long min = 1; 
        
        while(min <= max) {
            long mid = (max + min) / 2;
            
            long sum = 0; // 처리할 수 있는 사람 수 (long)
            // mid 값으로 times 배열의 시간 값을 가진 심사관들이 몇명 심사할 수 있는지
            for(int time : times) {
                sum += mid / time;
            }
            
            if(sum < n) {
                min = mid+1;
            } else {
                max = mid-1;
                answer = mid;
            }
        }
        
        return answer;
    }
}

📖 Solution

처음 1시간 동안 푼 방법은 이분탐색이 아니였지만 그 방법은 실패 -> 이분탐색으로 품

다시 이분탐색을 사용해 풀었더니 몇 개의 테스트 실패 -> sum의 type을 long으로 바꿔주었더니 통과!

💡 이분 탐색

left와 right를 정하고 그 중간값 mid값을 정한다.
그 뒤 찾고 싶은 값이 mid보다 크면 left를 mid로 바꾸고 다시 left와 right를 기준으로 찾는다.
반대로 찾고 싶은 값이 mid보다 작으면 right값을 mid값으로 바꾸고 찾는다.

여기서 max는 times를 오름차순으로 정렬 시킨 후 가장 뒤에서 n명 만큼만 곱하면된다 (최악의 경우수)

sum은 mid 값으로 times 배열의 시간 값을 가진 심사관들이 몇명 심사할 수 있는지를 나타낸다.

1. 처음에 max, min, mid값을 정함

2. mid 시간안에 처리할 수 있는 총 사람수를 구함 = sum

3. sum(처리할 수 있는 사람수)와 n(처리해야되는 사람수)를 비교함

   • sum이 n보다 많으면 시간을 너무 여유있게 잡았음 -> 시간을 줄여봄

   • sum이 n보다 적으면 시간을 너무 빡빡하게 잡았음 -> 시간을 늘려봄

4. sum과 n이 같으면 answer!