[이분 탐색, 난이도 중] 프로그래머즈, 입국심사

이 문제는 시간 복잡도 O(n)도 통하지 않는다.

인구 수, 심사 시간 데이터 범위가 10억이기 때문에 이분 탐색을 적용해야 하는 변수는 이 둘중 하나임을 알 수 있다.

 

이분 탐색 알고리즘은 IT계열의 대학교에서 대부분 1학년때 배울 것이다.

"1000개의 수중 하나를 선택했을 때 10번 이내의 yes or no 질문으로 선택한 수를 찾을 수 있다" 이런 기초적인 예시로 많이 배웠을거라 생각이 든다. 여기서 핵심은 탐색 조건은 yes or no라는 것이다.

이분 탐색은 중간값을 기준으로 찾으려는 값이 큰가 or 작은가로 판단하여 탐색이 이루어진다.

찾으려는 값이 크다면 첫 번째 값~ 중간 값 까지는 찾으려는 수가 없다는 의미이고,

찾으려는 값이 작다면 중간 값~ 마지막 값 까지는 찾으려는 수가 없다는 의미이다.

탐색할 때마다 무려 50%의 경우를 배제할 수 있는 것이다.

이분 탐색은 이렇게 O(logn)의 시간복잡도로 원하는 값을 찾을 수 있다.

이 문제에도 yes or no를 적용하여 풀어보자.

 

중간값을 정해야 하는데 적당히 근사적으로 정해도 된다.

answer의 최솟값은 1이고,

answer의 최댓값은 times의 최댓값에 대기 인원수를 곱한 값이 된다.

이 (최솟값+최댓값)/2 을 중간값으로 정하면 된다.

 

중간값 만큼의 시간이 주어졌을 때 심사관 당 심사할 수 있는 인원 수들의 합 sum을 구하면 되는데,

여기서 sum이 n보다 크다면 "크다" 라는 이분 매칭 조건에 답할 수 있게 되는 것이다.

그렇다면 n명을 모두 심사하는데에는 적어도 중간값보다는 더 적은 시간이 걸리는 뜻이므로

중간값~마지막 값을 정답 후보에서 배제하고, 최댓값을 중간값-1로 설정한다.

또한, sum이 n보다 작다면 "작다" 라는 이분 매칭 조건에 답할 수 있으며,

첫 번째값~ 중간값을 정답 후보에서 배제하고, 최솟값을 중간값+1로 설정한다.

 

이 과정을 최솟값이 최댓값을 따라 잡을 때 까지 반복하면 된다.

answer을 최댓값으로 두고 시작했기 때문에 sum이 n이상일 경우에는 answer값을 mid값으로 계속 업데이트 해나갔다.

앞에서도 설명했지만, 찾으려는 수가 mid 이상에는 없기 때문에 answer값을 mid값으로 둠으로써, 반복마다 탐색 범위의 최댓값을 유지해나가려는 것이다.

 

일단 

테스트 케이스 9개 모두 통과

 

#include <vector>
#include <algorithm>
using namespace std;

long long solution(int n, vector<int> times) {
    sort(times.begin(),times.end());
    long long mini = 1;
    long long mid,sum;
    long long maxi = (long long)times[times.size()-1]*n;
    long long answer = maxi;
    while(mini<=maxi){
        sum=0;
        mid=(mini+maxi)/2;
        for(int i=0;i<times.size();i++) sum+=(long long)(mid/times[i]);
        if(sum>=n){
            if(answer>mid) answer=mid;
            maxi = mid-1;
        }
        else mini = mid+1;
    }
    return answer;
}