[PS] 입국심사

문제

프로그래머스

- 모든 사람이 심사를 받는데 걸리는 시간의 최솟값 구하기

 

풀이

고득점 Kit에서 이분탐색으로 분류된다

기본적으로 이분탐색은 최솟값/최댓값 탐색, 또는 TTTFFF 로 이분적으로 분류되는 경우에 사용할 수 있는 알고리즘이다

 

순차탐색에 비해서 탐색 범위를 절반으로 좁혀가면서 찾기 때문에 O(logN)의 시간 복잡도를 가진다

따라서 하나의 특징이 있는데, 대부분의 문제에서 데이터의 범위가 엄청 큰 편이다

(제한 사항: 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하)

 

이런 경우에 여기서 힌트를 찾아서 이분 탐색으로 풀어야 한다는 아이디어를 얻을 수도 있겠다

 

 

이분탐색의 경우에는 이분적으로 나뉘는 기준을 찾아서, min과 max를 설정해주는게 풀이의 시작이다

이 문제에서 입출력 예시를 보면, 시간이 지남에 따라 입국심사를 완료한 사람이 늘어난다

따라서 이걸 보고 "시간"이 기준이 된다는 것을 유추할 수 있다!

 

예를 들어, 심사에 걸리는 시간이 30분이라고 가정하자

A가 심사에 7분이 걸리고, B는 심사에 10분이 걸린다

 

그럼 A의 경우부터 살펴봤을 때

30/7 = 4명을 심사할 수 있고

B는 30/10 = 3명을 심사할 수 있으므로

총 7명을 심사 가능하다!

 

이런 식으로 "시간"을 이분탐색으로 줄여나가면서 탐색할 수 있다

 

 

코드

#include <algorithm>
#include <string>
#include <vector>

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    sort(times.begin(), times.end());

    long long min = 1;
    long long max = n * (long long)times.back();
    
    while (min <= max) {
        long long mid = min + (max - min) / 2;
        long long tmp = 0;

        for (int i = 0; i < times.size(); i++){
        	tmp += (mid / (long long) times[i]);
            if (total_people >= n) break;
        }
		
        if (tmp >= n) {
            max = mid - 1;
            answer = mid;
        }
        else min = mid + 1;
    }
    
    return answer;
}

 

 

회고

이분 탐색 알고리즘을 몰랐을 때는 어떻게 푸는지 계속 헤맸는데

알고리즘을 공부하고 나서 다시 보니까 가장 기본적인 유형인 것 같다!