[프로그래머스 / Level3] 입국 심사 (Java)

문제에서 큰 값이 나올 수 있으면 long 사용 여부를 확인하자.

문제 보기

사용한 것

• 시간 복잡도를 해결하기 위한 이진탐색 사용.

풀이 방법

• 입국 심사를 기다리는 사람은 최대 1,000,000,000명, 한 사람당 최대 심사 시간은 1,000,000,000분이다. 일반적인 풀이로는 시간 초과니 이진탐색을 사용한다.
• 특정 시간안에 n명의 사람이 모두 심사를 마칠 수 있는지 판단하는 건 쉽다.
  • (특정 시간 / 입국 심사에 걸리는 시간)을 계속해서 더해주면 최대로 심사할 수 있는 사람의 수가 나온다.
• 그렇다면, 특정 시간을 기준으로 이진탐색을 수행하면 O(n * Log(n)) 시간 복잡도로 풀이 가능하다. (이진탐색 = O(Log(n)), 가능 여부 = O(n))
• 특정 시간안에 가능한지 판별하기 위해
  • l = 1, r = long 최대 값으로 이진탐색
  • m만큼의 시간에 대해 가능여부 판별
    • 심사원 별로 해당 시간안에 심사 가능한 사람 수를 계산
    • 계속 더해주면서 심사할 사람 수보다 넘으면 true 반환
    • 심사할 사람 수를 넘지 못하면 false 반환
• 모두 끝나면 l return

코드

class Solution {

    int n;
    int[] times;

    public long solution(int n, int[] times) {
        this.n = n;
        this.times = times;

        long l = 1;
        long r = Long.MAX_VALUE;
        long m;
        while (l <= r) {
            m = l + (r - l) / 2;

            if (isPossible(m)) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }

        return l;
    }

    boolean isPossible(long limit) {
        long num = 0;
        for (int time : times) {
            num += limit / time;
            if (num >= n) {
                return true;
            }
        }

        return false;
    }
}