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

시간을 알면 인원수를 쉽게 구할 수 있고, 숫자의 범위가 매우 크므로 이분탐색을 생각할 수 있다.

놓친점 1

"정렬", 정렬을 놓쳤다... 풀어놓고 왜틀렸지.. 시간낭비했다. 코테에서는 절대 절대 주의하자.

놓친점 2

right를 쉽게쉽게 설정할 수 있는 문제만 만나봤는데 이 문제는 꽤 섬세하게 right를 설정해줘야 풀 수 있었다. 한번더 생각하고 풀어보자

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

코드

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long answer = Long.MAX_VALUE; // 최솟값찾기
        Arrays.sort(times);
        int length = times.length;
        
        long left = 0;
        long right = times[times.length-1] * (long)n;
        while(left <= right){
            
            long mid = (left+right)/2;
            long cnt = 0;
            
            for(long time : times){
                cnt += mid/time;
            }
            
            // cnt 명 참여가능
            if(cnt >= n){
                 //System.out.println(String.valueOf(mid)+" " + String.valueOf(cnt)+"이므로 증가");
                answer = Math.min(answer, mid);
                right = mid-1;   
            }
            else{
                //System.out.println(String.valueOf(mid)+" " + String.valueOf(cnt)+"이므로 감소");
                left = mid+1;
            }
        }
        
        return answer;
    }
}