[프로그래머스] 입국심사 (JAVA)

[풀이]

이 문제는 이진 탐색(Binary Search)을 활용하여 효율적으로 해결할 수 있다.

문제의 핵심은 각 심사관의 처리 속도(times 배열)와 사람 수(n)를 고려하여, 모든 사람이 심사를 받을 수 있는 최소 시간을 계산하는 것이다.

최소 시간을 구하기 위해서 시간의 범위를 탐색해야 한다.

이 때 시간을 직접 하나씩 늘려가며 확인하는 완전 탐색은 비효율적이다.

심사를 받는데 걸리는 최소/최대 시간을 아래와 같이 설정할 수 있으므로 탐색의 범위가 좁혀진다.

따라서 이진 탐색을 생각하게 된다.

• 최소 시간: 1분 (최소한의 시간)
• 최대 시간: 가장 느린 심사관이 모든 사람을 처리하는 경우 n×max(times)

이진 탐색은 정렬된 범위에서 특정 조건을 만족하는 최적의 값을 찾는 문제에 적합하다.

 

이진 탐색 알고리즘에 대한 자세한 설명은 아래 링크를 통해 확인할 수 있습니다.

https://tnwlswkd.tistory.com/112

[ 알고리즘] 이분탐색(Binary Search)

 

 

이진 탐색을 구현하기 위해 

low 값을 최소 시간, high 값을 최대 시간으로 설정해두었다.

그리고  calcPersonCount에서  mid에 해당하는 시간에 총 몇명을 심사할 수 있는지 계산했다.

이 때 아래 사진과 같은 문제를 해결하기 위해 심사 가능한 사람이 이미 n명을 넘었다면 반복문을 빠져나오도록 했다.

 

mid 시간에 해결할 수 있는 사람이 n명 보다 많으면 더 짧은 시간을 탐색하기 위해 high 값을  mid -1로 업데이트 하고

n명보다 적으면 더 긴시간을 탐색하기 위해 low 를 mid + 1 로 업데이트 해주었다.

personCnt == n인 경우에도 탐색을 계속하는 이유는 더 작은 시간에서 조건을 만족하는지를 확인하기 위해서이다.

 

위의 과정을 반복하며 모든 사람을 심사하기 위한 최소시간을 계산해주었다.

 

 

[시간 복잡도]

 

• 시간 복잡도: O(log(max(times) × n) × m)
• 주요 원인:
  • 이진 탐색: O(log(max(times) × n))
  • 심사관 수 계산: O(m)
• 최악의 경우 계산량: 약 6,000,000 연산
• 결론: 제한 조건에서도 실행 가능합니다.

 

 

[코드]

import java.util.Arrays;

class Solution {
    public long solution(int n, int[] times) {
        long low = 1;
        long high = (long) Arrays.stream(times).max().getAsInt() * n; 
        long answer = high;

        while(low <= high) {
            long mid = (low + high) / 2;
            long personCnt = calcPersonCount(mid,n,times);
            if(personCnt >= n) {
                answer = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return answer;
    }

    public long calcPersonCount(long curTime ,int n, int[] times){
        long personCnt = 0;
        for(int time : times) {
            personCnt += curTime / time;
            if(personCnt > n)   break;
        }
        return personCnt;
    }
}

[문제]

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