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

문제

 

 

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

using namespace std;



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

 

 

문제 접근 순서

 

1. 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 구하는 것이 문제의 목표라는 것을 파악했습니다. 

 

2. 시간복잡도에 대해 생각해보니 일단 완전탐색 알고리즘으로는 효율적이지 않음을 확인 했습니다. 

    왜냐하면 임국심사를 기다리는 사람들과 각 심사관의 인구수 범위가 10^8을 넘기 때문에 

    완전 탐색으로 한다면 시간복잡도상 time Limit가 걸리기 때문입니다. 

 

3.  따라서 시간을 오름차순으로 정렬하고 특정 Target(시간) 값을 찾는 문제이므로 

     Binary_search 알고리즘을 생각하였습니다. 

 

4. 해당 이분탐색을 생각한 후 다음으로는 어떤 것을 Target으로 잡을지가 문제였습니다.

    아무래도 연속된 값이여야 Target값을 찾는데 더 유리하므로, 시간을 기준으로 잡기로 했습니다. 

 

5. mid 값이 현재 주어진 시간이고 해당 주어진 시간으로 각각 몇명을 심사할 수 있는지 정리했습니다.

    그 결과 해당 심사할 수가 주어진 사람보다 많다면 시간이 더 줄어도 된다는 의미이므로 

    right  = mid -1 을 하였고 만약 주어진 사람보다 저 적다면 시간이 늘어야 하므로 left = mid +1 을 하였습니다. 

 

    아마 이 문제의 핵심은 바로 주어진 시간에 각각의 심사관이 몇명을 해결할 수 있는지를 통해

    이진탐색의 기준을 어떤 것으로 잡을지 생각할 수 있느냐 없느냐에 대한 점인것 같습니다.