231115 - 이분탐색 : 입국심사

[robert-min]

https://school.programmers.co.kr/learn/courses/30/lessons/43238?language=java

입국심사

• 포인트 : 입력값이 매우 크고, 모든 사람이 심사를 받는데 걸리는 시간의 "최솟값" 특정 값을 찾는 문제일 경우 이분탐색을 고민
• 풀이 :
  1. 가장 오래걸리는 시간은 가장 오래걸리는 심사대에서 모든 사람이 심사를 받는 경우로 이를 right으로 설정
  2. 이분탐색을 진행
     • 주의할점 : 입국심사를 다 받은 사람이 n 명이상이 되어야만 조건에 맞기 때문에 right이 이동하는 S >= n인 경우에 answer 갱신

import java.util.*;

class Solution {
    static long left, right;

    public long solution(int n, int[] times) {
        long answer = 0;

        // 1
        Arrays.sort(times);
        left = 1;

        // 최대 시간 : 가장 오래 걸리는 심사대에서 모든 사람이 심사를 받는 경우
        right = (long) times[times.length - 1] * (long) n;

        // 2
        while (left <= right) {
            long mid = (left + right) / 2;
            long S = 0;
            for (long t : times) {
                S += (mid / t);
            }

            if (S >= n) {
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return answer;
    }
}