프로그래머스: 입국심사

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

프로그래머스

설명

이 문제를 풀 때, 입국 심사를 어디에 맞출 것인가를 고민하는 것이 아닌 현재 시간을 기준으로 최대 몇명이 마칠 수 있을 것인가에 초점을 맞추면 된다.

minTime을 1이고, 

maxTime은 times 배열에서 가장 큰 수 * n명 

=> minTime이 times 배열의 가장 작은 수 * n으로 하면 안되는 이유는 동시에 입국 심사를 받을 수도 있기 때문!!!

 

minTime과 maxTime의 중간값을 가지고 최대 몇명이 마칠 수 있을 것인지 구한다. 

• 만약 입국심사를 받을 수 있는 사람이 n명 이하라면? => minTime을 averageTime + 1이 되고
• 만약 입국심사를 받을 수 있는 사람이 n명 이상이면? => maxTime을 averageTime - 1이 된다. 

이렇게 이분탐색을 통해 최대 몇명이 마칠 수 있을지 구하면 된다.

 

=> 입국심사를 기다리는 사람이 1,000,000,000 이하이므로 탐색으로는 시간초과 발생할 것이고

=> 그러니 이분 탐색을 사용하고

=> 큰 범위이므로 long을 사용하자!

코드

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        
        Arrays.sort(times);
        long min = 1;        
        long max = (long) times[times.length - 1] * n;
        answer = max;
        
        while(min <= max) {
            long average = (min + max) / 2;
            long tmp_n = 0;
            
            for(int i = 0; i < times.length; i++) {
                tmp_n += average / times[i]; // 몇명까지 받을 수 있는지
                if(tmp_n > n) break;
            }
            
            if(tmp_n < n) min = average + 1;
            else {
                answer = Math.min(answer, average);
                max = average - 1;
            }
        }
        
        return answer;
    }
}

 

Reference

• https://blog.naver.com/gkswlcjs2/223201657964