[PGS] 프로그래머스 - 입국심사 (JAVA)

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

프로그래머스

import java.util.*;
import java.io.*;

class Solution {
    public long solution(int n, int[] times) {
        long answer = Long.MAX_VALUE;
        Arrays.sort(times);
        long left = 0;
        long right = times[times.length-1] * (long)n;
        
        while(left<=right){
            long mid = (left+right) / 2;
            long complete = 0; //총 심사한 인원
            for(int i=0;i<times.length;i++){
                complete += mid/times[i];
            }
            if(complete<n){ // 해야할 인원보다 적게 처리했을 때 => 시간이 더 필요하다
                left = mid+1;
            }
            else { //시간 남을 때 => 시간을 줄인다
                right = mid-1;
                answer = mid;
            }
        }
        return answer;
    }
}

1. 심사위원의 심사 시간을 정렬한다.

2. 가장 오래 걸리는 시간을 right로 설정 ( n * times[times.length-1])

3. left<=right인동안 심사한 인원을 구한다

     3-1. 해야할 인원보다 적게 처리한 경우 시간이 더 필요하므로 left=mid+1

     3-2. 그게 아닌 경우 시간을 줄인다. (right = mid-1)

4. while문을 탈출하면 answer를 return한다.

 

이분탐색을 활용한 문제였다. 이분탐색에 대해 공부하였다.

이분탐색 https://tech-heng.tistory.com/84