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

💡문제 분석 요약

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 주어질 때, 모든 사람이 심사는 받는데 걸리는 시간의 최솟값을 구하는 문제이다.

• $1 ≤ n ≤ 1,000,000,000$
• 각 심사관이 한 명을 심사하는데 걸리는 시간(분): $1 ≤ time ≤ 1,000,000,000$
• 심사관: $1≤ t ≤ 100,000$

 

💡알고리즘 설계

이진탐색을 사용.

• 탐색 범위
  • left(최소시간): 1
  • right(최대시간): `n * max(times)` :가장 오래 걸리는 심사관이 모든 사람을 심사하는 경우
• 탐색 수행
  • mid(중간시간): `left + (right - left) / 2`
  • 이 시간동안 모든 심사관들이 심사할 수 있는 인원을 계산한다.
• 범위 조정
  • 계산된 인원이 n보다 작은 경우 → 시간이 부족함 ⇒ `left = mid + 1`
  • 계산된 인원이 n보다 큰 경우 → 시간이 충본함 ⇒ `right = mid - 1`, `anwswer = mid` 갱신
• left가 right보다 작거나 같을 때까지 위 과정을 반복한다.

 

💡코드

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        long left = 1;
        long right = (long)n * Arrays.stream(times).max().getAsInt();
        long mid = 0;
        while(left <= right) {
            mid = left + (right - left) / 2;
            long count = 0;
            for(int time : times) {
                count += mid / time;
            }
            if(count < n) left = mid + 1;
            else {
                right = mid - 1;
                answer = mid;
            }
        }
        return answer;
    }
}

 

💡시간복잡도

• 이진탐색에서 $n * max(times)$를 $M$이라고 할 때, $O(log M)$
• 각 단계에서 심사 가능한 인원 계산 시, 심사관 수를 $k$라고 할 때 $O(k)$

따라서 전체 시간복잡도는 $O(k * log M)$ 이다.

 

💡 틀린 이유

1. `count` 를 int로 선언해 오버플로우가 발생했다. → long으로 변경

2. `right` 값을 초기화할 때 `n`을 long으로 변환하지 않아 오버플로우가 발생했다.

 

💡 틀린 부분 수정

1. `count` 를 int로 선언해 오버플로우가 발생했다.

수정 전

int count = 0;

 

수정 후

long count = 0;

 

 

2. `right` 값을 초기화할 때 `n`을 long으로 변환하지 않아 오버플로우가 발생했다.

수정 전

long right = n * Arrays.stream(times).max().getAsInt();

 

수정 후

long right = (long)n * Arrays.stream(times).max().getAsInt();

 

💡 느낀점 or 기억할정보

이 문제를 어떻게 이진탐색으로 풀어야할지 막막했다. 결국 혼자 생각해내지 못하고 Claude에서 힌트를 받아가며 설계했다ㅠ 이진탐색의 과제가 아니었다면 이 문제가 이진탐색 문제라는 것도 몰랐을 것 같다…

큰 수를 다룰 때 형변환의 중요성을 다시 느꼈다. 예시 입력은 큰 숫자가 아니어서 큰 문제 없이 통과했지만 제출했을 때 테스트 케이스 절반이 틀렸다고 나왔다.

다른 문제에서도 틀렸을 때 형변환을 제대로 해주지 않아서 오버플로우가 발생한 건 아닌지 잘 체크해야겠다.