[programmers] 입국심사

문제 풀이 : 2021.05.06

풀이

n의 수가 1000000000명까지의 범위이므로 일반적인 재귀호출이나 반복문으로는 시간초과가 됨
최대,최소 사이에서 모든 사람들이 심사를 끝내는 시간을 찾음
times 배열을 오름차순으로 정렬 후 이진탐색 알고리즘 이용

코드

import java.util.*;
class Solution {
    public long solution(int n, int[] times) {
         Arrays.sort(times);
         long min=1;
         long max=(long)times[times.length-1]*n;
         long mid=0;
         long sum;
         long answer = max;
         while(min<=max){
             sum=0;
             mid=(min+max)/2;
             for(int t:times){
                 sum+=mid/t;
             }
             System.out.print(mid+ " " + sum+" answer : ");
             if(sum>=n){
                 if(mid<answer){
                     answer=mid;
                     
                 }
                 max=mid-1;   
                 System.out.println(answer+" min,max : "+min+" "+max);
             }
             else{
                 min=mid+1;
                 System.out.println(answer+" min,max : "+min+" "+max);
             }
         }
         return answer;
    }
}

문제 출처 링크