[Programmers] 입국심사 - Java

문제

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

프로그래머스

 

풀이

입국심사의 심사대에서 심사하는 시간이 주어지는데, n명 사람들이 입국 심사를 받는데 걸리는 최소 시간을 구하는 문제이다.

 

데이터 범위를 보자.

입국심사를 받는데 사람들의 수: 최대 10억

심사를 받는 시간: 최대 10억

심사대: 10만

 

10억이라는 데이터를 처리하는 과정에서 로그연산으로 끝낼 수 있는 알고리즘을 사용해야한다.

 

이분탐색을 사용하면 된다.

범위를 좁혀가면서 n명을 mid시간 이내에 처리가 되는가?를 계속 물어보면 된다고 생각했다.

mid로 처리가 가능하면 시간을 조금 더 줄여서 처리가 되는가?

mid로 처리가 불가능하면, 시간을 조금 더 크게하면 처리가 되는가?

이 두가지 원리라고 생각했다.

 

데이터가 10억 * 10만이므로, 이분탐색으로 로그연산을 해도 60이내의 숫자가 나온다.

60 * 100000 => 600만 연산으로 문제를 해결할 수 있다.

 

이 문제에서 범위를 잘 생각해봐야한다.

최소는 1이다.

최대는 (심사를 받는 시간(최대 10억) * 심사대 갯수)이다.

 

1. 이분탐색의 최대 최소값을 초기화 해준다.

 

2. mid를 구해서 mid시간에 심사대에서 n명 이상의 사람들을 심사할 수 있는지 확인한다.

심사를 할 수 있는 경우 => 시간을 줄여본다.

심사를 할 수 없는 경우 => 시간을 늘려본다.

 

3. 마지막에 end의 값은 mid -1이 되었을 것이므로, 최솟값은 end + 1이 된다.

마지막에 -1을 한번 더 해줬으므로, 주의해야한다.

 

소스코드

class Solution {
    public long solution(int n, int[] times) {
        long start = 1L;
        long end = 1_000_000_000 * (long) n;
        
        while (start <= end) {
            long mid = (start + end) / 2;
            
            if (check(mid, n, times)) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        
        return end + 1;
    }
    
    private boolean check(long mid, int n, int[] times) {
        long cnt = 0;
        
        for (int time : times) {
            cnt += (long) (mid / time);
        }
        
        return cnt >= n;
    }
}

 

실행결과