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

 

 

 

 

 

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

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

 

이번 문제는 이분 탐색 문제였습니다.

 

 

 

 

 

📝 문제 풀이

1. 이분 탐색을 하기 위해 n명을 심사하는데 걸리는 최소 시간과 최대 시간 정의 (최소 시간: left_val, 최대 시간: right_val)

2. mid 시간 동안 심사 가능한 사람 수가 n명 보다 적으면 시간 범위를 늘림 ← left_val = mid + 1

3. mid 시간 동안 심사 가능한 사람 수가 n명 보다 크거나 같으면

     (1) 시간 범위를 좁힘 ← right_val = mid - 1

     (2) mid 값은 answer이 될 수있으므로 answer = mid

 

 

 

 

 

👩🏻‍💻 C++ 코드

#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_val = times[0];
    long long right_val = (long long)times[times.size() - 1] * n;
    
    while(left_val <= right_val) {
        long long possible = 0;
        long long mid = (left_val + right_val) / 2;
        
        for (int i=0; i<times.size(); i++)
            possible += mid / times[i];
        
        // mid 시간 동안 심사 가능한 사람 수가 n명보다 적으면 
        if (possible < n) {
            left_val = mid + 1;
        } else {
            right_val = mid - 1;
            answer = mid;
        }
    }
    
    return answer;
}

 

프로그래머스 - 결과 화면