[JAVA] 입국심사 - 프로그래머스[Lv.3]

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

프로그래머스

---

import java.util.*;
class Solution {
    static long cnt;
    public long solution(int n, int[] times) {
        long answer = 0;
        Arrays.sort(times);
        long left = 0;
        long right = (long) times[times.length - 1] * n;

        while(left <= right){
            long mid = (left + right) / 2 ;
            cnt = getTotal(times, mid);
            if(cnt >= n){
                answer = mid;
                right = mid - 1;
            }else
                left = mid + 1;
        }
        return answer;
    }
    private static long getTotal(int[] times, long total){
        long cnt = 0;
        for(int time : times){
            cnt += total / (long) time;
        }
        return cnt;
    }
}

💡 이분 탐색

풀이

• 이분 탐색에 사용할 인덱스를 소요 시간으로 두고 최소 시간을 찾아 나가야 함!
• 이때 문제조건 상, 변수형 long으로 선언해서 오버플로우 방지 (형 변환 주의)
• 오른쪽으로 탐색할지, 왼쪽으로 탐색할지 판단 기준 ➡️  해당 시간(mid)에 각 라인에서 심사 가능한 총 사람 수(cnt)
  • cnt >= n 인 경우, 시간을 줄여줘야 함
    
    • answer = mid 갱신
    • right = mid - 1 로 갱신
  • cnt < n 인 경우, 시간 모자르므로 오른쪽 탐색
    • left = mid+1

cnt == n 일 경우만, answer 갱신하면 틀리는 이유

[반례] n = 59, times=[1,1]  ;  answer=30
 -  mid = 29 / cnt = 58 -> left = 30, mid = 30 / cnt = 60  이 경우 answer이 갱신 불가능함
  ➡️ 나머지로 인해 cnt == n인 경우를 스킵하고 n에 가장 가까운 cnt가 정답처리 되는 경우가 있음!!
❗ ❗ 어차피 mid는 정답에 가깝게 항상 갱신되므로 cnt >= n일 경우 계속 갱신해줄 것