본문으로 건너뛰기

1. 문제 분석​

1.1 핵심 요구사항​

  • n명의 사람이 입국심사를 받아야 함 (n: 입국심사를 기다리는 사람 수)
  • m명의 심사관이 있음 (m: 심사관의 수)
  • 각 심사관마다 심사 시간이 다름
  • 심사관은 한 번에 한 명만 심사 가능
  • 모든 사람이 심사를 받는데 걸리는 최소 시간을 구해야 함
  • 사람들은 빈 심사대를 자유롭게 선택 가능

2. 문제 해결 접근 방식​

  • 먼저 제한사항을 자세히 살펴보겠습니다
    • n(입국심사 대기자 수): 1 ~ 1,000,000,000 (10억)
    • m(심사관 수): 1 ~ 100,000
    • 심사 시간: 1 ~ 1,000,000,000

2.1 시뮬레이션 접근​

// 각 사람마다 가장 빨리 끝나는 심사대를 찾아 배정
for(int i = 0; i < n; i++) {
    // 각 심사대의 종료 시간을 확인
    // 가장 빨리 끝나는 심사대에 배정
}
  • 문제점: n이 10억이므로 시간 초과
  • O(n × m) ≈ O(10^9 × 10^5)는 실행 불가능

2.2 우선순위 큐를 활용한 접근​

// 우선순위 큐로 가장 빨리 끝나는 심사대 관리
PriorityQueue<Long> pq = new PriorityQueue<>();
  • 문제점: 여전히 n번의 반복 필요
  • O(n × log m) ≈ O(10^9 × log 10^5) 역시 너무 큼

2.3 파라메트릭 서치 접근​

  • 파라메트릭 서치는 최적값을 찾기 위해 이진 탐색을 활용하는 방법입니다.
  • "처리하는데 걸리는 최소 시간은 얼마인가?"라는 최적화 문제를
    • "X시간 안에 모든 사람을 처리할 수 있나요? (Yes/No)"라는 결정 문제로 바꿉니다.
    • 결정 문제란 Yes 또는 No로 답할 수 있는 문제를 말합니다.
  • 이렇게 바꾸면 다음과 같은 특징이 생깁니다:
    • 만약 7시간 안에 모든 사람을 처리할 수 있다면, 8시간, 9시간에도 당연히 처리할 수 있습니다.
    • 반대로 7시간 안에 처리할 수 없다면, 6시간, 5시간에도 처리할 수 없습니다.
    • 이처럼 답이 Yes인 지점과 No인 지점 사이에 명확한 경계가 있어 이진 탐색이 가능해집니다.

결정 문제

boolean determine(int[] times, long timeLimit, int n) {
    long people = 0;
    
    for(int time: times) {
        people += timeLimit / time;
        if(people >= n) return true;  // 최적화: 충분한 인원을 찾으면 바로 반환
    }
    
    return people >= n;
}
  • 입력된 시간(timeLimit) 동안 n명을 모두 심사할 수 있으면 true, 없으면 false를 반환합니다.
팁

다음과 같은 특성을 가진 문제라면 파라메트릭 서치 접근을 고려해보세요:

  1. 최적화 문제를 Yes/No 문제로 바꿀 수 있음
  2. Yes/No의 경계가 명확한 지점이 있음 (경계를 기준으로 한쪽은 모두 Yes, 다른 쪽은 모두 No)
  3. 답의 범위가 큰 경우(완전 탐색 불가능)

2.4 시간 복잡도 분석​

이진 탐색 접근법의 시간 복잡도:

  • 답의 범위: 0 ~ 10^18 (최대 심사시간 × 인원)
  • 이진 탐색의 단계: O(log 10^18) ≈ O(60)
  • 각 단계에서의 연산: O(m), m은 심사관 수
  • 최종 시간 복잡도: O(log(10^18) × m) ≈ O(60 × 10^5)
정보

n이 10억이라는 제한사항이 결국 파라메트릭 서치 접근법을 도출하는 핵심 힌트였습니다. 다른 접근법들은 모두 n에 비례하는 시간 복잡도를 가져 실패할 수밖에 없습니다.

3. 문제 풀이​

3.1 풀이 전략​

  1. 답이 될 수 있는 시간의 범위 설정
  2. 이진 탐색으로 가능한 최소 시간 탐색
  3. 각 시간에 대해 처리 가능한 인원을 계산하여 조건 만족 여부 확인

3.2 구현 코드​

class Solution {
    public long solution(int n, int[] times) {
        long low = -1L;
        long high = 1000000000000000000L;
        
        // 이진 탐색으로 최소 시간 찾기
        while(low + 1 < high) {
            long mid = (high - low) / 2 + low;
            if(determine(times, mid, n)) {
                high = mid;
            } else {
                low = mid;
            }
        }
        return high;
    }
    
    // 주어진 시간 내에 n명을 처리할 수 있는지 확인
    private boolean determine(int[] times, long timeLimit, int n) {
        long people = 0;
        
        for(int time: times) {
            people += timeLimit / time;
            if(people >= n) return true;  // 최적화: 충분한 인원을 찾으면 바로 반환
        }
        
        return people >= n;
    }
}

3.3 코드 설명​

  1. 이진 탐색 범위 설정
    • low: 불가능한 시간의 최댓값 (-1부터 시작)
    • high: 가능한 시간의 최댓값 (10^18)
    • low + 1 = high가 될 때까지 반복
  2. 판정 함수 구현
    • 주어진 시간 내에 처리 가능한 총 인원 계산
    • 각 심사관이 처리할 수 있는 인원 = 전체 시간 / 심사관별 처리 시간
    • 오버플로우 방지를 위해 long 타입 사용
    • 최적화: n명 이상 처리 가능하다는 것이 확인되면 early return
  3. 최적화 포인트
    • 이진 탐색 구현 시 오버플로우 주의
    • 불필요한 계산을 줄이기 위한 early return
    • (mid = low + (high - low) / 2) 대신 (mid = (high - low) / 2 + low) 사용하여 오버플로우 방지

4. 마치며​

  • 이 문제는 큰 입력값(n = 10억)이라는 제한사항을 통해 파라메트릭 서치 접근법을 도출할 수 있었습니다.
  • 처음에는 직관적인 시뮬레이션이나 그리디 접근을 생각할 수 있지만, 시간 복잡도를 계산해보면 실패할 수밖에 없습니다.
  • 문제의 제한사항을 꼼꼼히 살펴보고, 이를 통해 적절한 알고리즘을 선택하는 것이 중요합니다.