[프로그래머스] 입국 심사 (이분탐색)

문제 소개

오늘 풀었던 프로그래머스 - 입국심사 문제를 정리합니다.

이 문제는 여러 심사관이 있을 때, 모든 사람이 심사를 완료하는 데 걸리는 최소 시간을 구하는 문제입니다.
심사 시간이 다르기 때문에, 각 심사관별로 동시에 심사할 수 있다는 점을 활용해야 합니다.

문제 링크: 입국심사 - 프로그래머스

사다리 조작 - 백준 15684번

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 심사 시간이 다양한 상황에서, 가능한 심사 완료 시간을 이분 탐색으로 좁혀갑니다.
2. 현재 시간(mid) 안에 몇 명을 심사할 수 있는지 계산합니다.
3. 심사할 수 있는 인원 수가 n명 이상이면 시간을 줄이고, 부족하면 시간을 늘립니다.

---

해결 과정 및 코드

핵심 아이디어

1. left: 가능한 최소 시간 (1분)
2. right: 가능한 최대 시간 (가장 느린 심사관 시간 × 전체 인원 수)
3. mid: 중간 시간 후보
4. mid 시간 동안 처리할 수 있는 사람 수를 계산하여, n명 이상 처리 가능한지 확인한다.

코드

시간 복잡도 : O(log(최대 시간) × 심사관 수)

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long left = 1;
        long right = (long) Arrays.stream(times).max().getAsInt() * n;
        long answer = right;

        while (left <= right) {
            long mid = (left + right) / 2;
            long total = 0;
            for (int time : times) {
                total += mid / time;
                if (total >= n) break;
            }
            if (total >= n) {
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return answer;
    }
}

 

추가: "왜 이분 탐색을 쓰는가?"

• 이 문제는 '시간'을 대상으로 탐색하는 문제입니다.
• 시간이 길어질수록 → 더 많은 사람을 심사할 수 있습니다. (단조 증가)
• "시간"에 대해 단조성을 가지기 때문에 → 이분 탐색을 쓸 수 있는 겁니다.
• 이분 탐색의 핵심은:
  "어떤 기준(mid 시간)에서 가능한지/불가능한지" 를 빠르게 판단하는 것!