프로그래머스 - 입국심사 - 이진탐색 - Java

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/43238

2. 풀이

이진탐색의 🚨KeyPoint는

1. 어떤 값을 이진탐색 할것인가
2. lowerBound인가, upperBound인가 (즉 범위를 어떻게 세울 것인가)

문제를 보면 이게 이진탐색 문제인가? 싶기도 하다. 일단 제한 사항의 범위가 크면 무조건. 이진탐색을 의심해봐야한다.

- 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
- 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
- 심사관은 1명 이상 100,000명 이하입니다.

이 문제는 심사를 받는데 걸리는 시간을 이분탐색 값으로 잡고 시작한다.

핵심 ✨Point

1. 시간의 최소값을 구하는 것이기 때문에 lowerBound를 사용한다.
   lowerBound : 찾고자 하는 값(이상의)값이 처음으로 나타나는 위치를 사용한다.
   참고 - 내 풀이

2. start, end
   start - 0 (1부터 진행해도 된다.)

   1초부터 시작을 하는것이죠 하지만 저는 times[0]을 start로 뒀습니다. 어차피 1초부터 해도 되지만 탐색의 시간을 줄이기 위해 답이 될 수 있는 수 중 가장 적은 시간인 times[0]으로 뒀습니다.
   참고 문헌

3. end
   end값은 가장 오래 걸릴 경우를 생각하면 된다. 이는 n명 모두가 가장 대기가 긴 심사원에게 심사를 맞는 것이다.
   🚨이렇게 되면 times배열의 정렬은 필수이다.🚨
   🚨int형인 n도 long으로 바꿔줘야 한다. 참고🚨

   long end = (times[times.length - 1] * (long) n) + 1;

3. 전체 코드

import java.util.*;

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