입국심사 **

사용 알고리즘: 이분탐색

사용 언어: java

 

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

class Solution {
    public long solution(int n, int[] times) {
        Arrays.sort(times);
        long answer = 0; 
        
        //평균 시간에 -> 한 심사대에서 -> 몇 명까지 심사할 수 있냐!!
        long left = 1;
        long right = times[times.length-1] * (long)n; //최대 이만큼 걸림!
        long mid = 0;
        
        while(left <= right) { //배열이 0분~times.length-1분까지인 느낌
            //현재 범위에서 최소로 걸리는 시간과 최대로 걸리는 시간의 평균으로 각각 계산해보기
            mid = (left+right) /2 ;
            System.out.println(right);
            
            long passenger = 0; //평균 시간 내 몇 명이나 심사할 수 있을까
            for(int t : times) {
                passenger += mid/t;
            }
            
            if(passenger < n) { //시간 내에 모든 사람을 심사할 수 없으면, 시간 늘리기
                left = mid+1;
            }
            else { //시간 내에 다 하고도 남는다면, 시간 줄이기
                right = mid-1;
                answer = mid;
            }
            
        }
        
        return left;
    }
}

 

 

이슈:

1. 최대 걸리는 시간 구하기(right에 해당), times 정렬하기를 제외하고이분탐색으로 이걸 어떻게 풀어야 하는지 감이 오지 않았다. -> 구글링 블로그 참고 후, 걸리는 시간을 일종의 배열처럼 보고 그 안에서 이분탐색을 하면 된다는 걸 깨달음!! (이분탐색이라 하더라도 주어지는 문제가 꼭 배열 형식이 아닐 수 있다!)

 

풀이 중 이슈:

1. 말도 안 되는 답이 나와서 확인해보니 right에 최대 걸리는 시간을 구해야지~해놓고 time.lenght-1..인덱스 번호만 넣어놨다.. 뭐지?

2. 고쳐도 안 됐는데 left, rigtht, mid의 타입을 int에서 long으로 변환했더니 답 나옴!