[프로그래머스/Level3] 입국심사

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/43238

문제 접근

이분 탐색을 알고리즘은 알았지만 이 문제에 어떻게 적용시켜야할 지를 몰랐다.
다른 분들의 답을 참고하여 어떤 식으로 접근해야하는지를 학습했다.
보통 이분 탐색은 해당 타겟을 찾으면 종료한다.
이 문제는 최소값을 찾는 것이기 때문에 start와 end가 교차할 때까지 진행해야한다.

이분 탐색 접근법

1. 탐색 구간을 정해야 한다. 이 문제에서는 총 걸리는 시간(0~times의 최대값 * n)
2. 찾을 타겟을 설정한다. 이 문제에서는 주어진 시간 안에 처리할 수 있는 사람의 수
3. 이분 탐색 진행

소스 코드

import java.util.Arrays;

class Solution {
    public long solution(int n, int[] times) {
        long minTime = Long.MAX_VALUE;
        long start, end, mid;
        long people;
        
        Arrays.sort(times);
        
        start = 0;
        end = (long)times[times.length - 1] * (long)n;
        
        while (start <= end) {
            mid = (start + end) / 2;
            people = 0;
            
            for (int time : times) {
                people += mid / time;
            }
            
            if (people >= n) {
                minTime = Math.min(minTime, mid);
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        
        return minTime;
    }
}