[프로그래머스 - Java] 입국심사

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

코딩테스트 연습 - 입국심사

 

풀이

 

이분탐색을 이용해서 해결하는 문제입니다. 이문제에서 중요한 것은 long형을 잘쓰는것!!!

저는 제 코드에서 9번째 줄에 

long maxT = (long)n * (long)times[len-1]; 

이부분에 처음에 (long)을 안붙였다가 계속 반타작하더니 붙이고 맞았습니다...

 

1. 우선 최소로 걸리는 시간은 1이고, 최대로 걸리는 시간은 가장오래걸리는 심사관에게 n명이 심사받는 경우인 n*Max(times)로 두었습니다.
2. 그런 뒤 이 값을 이용해 이분탐색을 시작합니다.
3. 이분탐색에서는 mid 시간동안 모든 심사관이 일할 때 최대 몇명이 심사받을 수 있는지 구합니다.
4. 심사 가능한 사람 수가 n보다 작은 경우 min = mid+1, 그 외의 경우엔 max = mid로 값을 업데이트하고 반복합니다.

 

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        int len = times.length;
        Arrays.sort(times);
        long minT = 1;
        long maxT = (long)n * (long)times[len-1];   //반드시 (long)써주기!!!
        
        //이분탐색 시작
        while(minT < maxT){
            long midT = (minT+maxT)/2;
            long sum = 0;                   //midT 시간동안 심사받는 사람
            
            for(int i=0; i<len; i++){
                sum += midT/times[i];
                if(sum > n)                 //n보다 커지면 더이상 안더해도 됨
                    break;
            }
            
            if(sum < n)
                minT = midT+1;
            else
                maxT = midT;
        }
        answer = Math.min(minT, maxT);
        return answer;
    }
}