[Programmers] 입국심사

 

❒ Description

---

날짜	2024.10.21 (월)
레벨	3
제목	입국심사
링크	https://school.programmers.co.kr/learn/courses/30/lessons/43238
알고리즘	Binary Search
시간 복잡도	O(nlog(n))

 

 

 

 

 

❒ Ideation

---

이번 문제에서는  아래와 같은 제한사항이 있기 때문에 가능한 최소한의 시간복잡도로 문제를 해결해야 한다.

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

1️⃣ 우선 심사에 걸릴 수 있는 최대 시간을 찾아야 한다.

2️⃣ 이분 탐색을 진행한다.

3️⃣ 이분 탐색 과정에서 선택된 시간에 최대 몇 명의 사람을 심사할 수 있는지 계산한다.

4️⃣ 처리할 수 있는 시간이 여러 개 존재할 경우 그 중 최소값을 출력해야 한다.

 

 

 

 

 

❒ 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 (left <= right) {
        long mid = left + (right - left) / 2;
        
        long canTakeCount = 0;
        for (int time : times) {
            canTakeCount = mid / time
        }
        
        if (canTakeCount < n) {
            left = mid + 1;
        } else {
            right = mid - 1;
            answer = Math.min(answer, mid);
        }
    }
    return answer;
}

 

 

 

 

 

---