[프로그래머스 / Level 3] 입국심사 (C++)

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

코딩테스트 연습 - 입국심사

입국심사를 기다리는 사람의 최대수가 10억명인것을 보면 for문을 사용해도 시간초과가 날수있다는 것을 생각하고 다른 방식의 풀이를 생각해야합니다.

 

문제 접근법

• for문으로 해결하기에는 인원수가 너무 많으므로 최소치와 최대치를 설정하고 중간값을 통해 최소, 최대치를 갱신하며 진행하는 이분탐색을 사용한다.
• 최소치는 1분 걸리는 심사관이 있을 때 입국심사를 기다리는 사람이 한명일 때다. (min = 1)
• 최대치는 10억분 걸리는 심사관이 한명일 때 입국심사를 기다리는 사람이 10억명일 때다. (max = 10억 x 10억)
• 중간값은 최소값과 최대값을 더한 값의 절반이다.
• 중간값과 times 배열의 값을 나눈값을 더한 뒤 이 숫자(count)를 n과 비교한다.
  • count값이 n보다 크거나 같다면, 시간내에 가능한 것이므로, 최대값을 중간값 - 1로 갱신한다.
    • 답이 중간값보다 큰 상태라면 중간값으로 변경해준다.
  • count값이 n보다 작다면, 시간내에 불가능한 것이므로, 최소값을 중간값 + 1로 갱신한다.
• 위 과정을 최소값이 최대값보다 작거나 같을때까지 진행한다.

아래는 코드입니다.

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
long long solution(int n, vector<int> times) {
    long long answer = 0;
    int len = times.size();
    
    sort(times.begin(), times.end());
    
    long long left = 1;
    long long right = (long long)times[len - 1] * n;
    answer = right;
    
    while(left <= right)
    {
        long long mid = (left + right) / 2;
        long long count = 0;
        
        for(int i = 0; i < len; i++)
            count += (mid / times[i]);
        
        if(count < n) 
            left = mid + 1;
        else
        {
            if(answer > mid) 
                answer = mid;
            right = mid - 1;
        }
    }
    
    return answer;
}