알고리즘(C++) / 프로그래머스 level 3 : 입국심사

level 3 : 입국심사

https://programmers.co.kr/learn/courses/30/lessons/43238?language=cpp 

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

 

코드

//프로그래머스 입국심사
#include <iostream>
#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 mid;

    while (left <= right) {
        mid = (left + right) / 2;

        long long count = 0; //mid 시간동안 심사 처리할 수 있는 사람 수

        for (int i = 0; i < times.size(); i++) {
            count += mid / times[i];
        }
        
        if (count < n) { //심사 할 수 있는 사람 수가 적을 때
            left = mid + 1;
        }
        else if(count >= n) { //심사 할 수 있는 사람 수가 많을 때
            answer = mid;
            right = mid - 1;
        }
    }

    return answer;
}

int main() {
    int n = 6;
    vector<int> times = { 7,10 };
    cout << solution(n, times) << "\n";
    return 0;
}

 

설명

이분탐색을 활용하여 이번 문제를 구현할 수 있다. 

이분탐색은 원하는 탐색 범위를 두 부분으로 분할해서 찾는 방식이다. 전부를 탐색하는 탐색 속도에 비해 빠르다. 

 출처 https://wootool.tistory.com/62 

[알고리즘] 이분 탐색

 

• 이분 탐색으로 left는 최소값 1, right는 최댓값 (times 가장 큰 수 x n) 이다. 
• count는 mid 시간동안 심사할 수 있는 사람의 수이다. 
• 심사할 수 있는 사람 수가 입국심사하는 사람보다 적을 때 left를 mid +1로 옮겨준다.
• 심사할 수 있는 사람 수가 입국심사하는 사람보다 많거나 같을때 right를 mid -1로 옮겨준다. 이때 시간을 answer에 저장해준다. 
• 이분 탐색은 left가 rigth보다 커질 떄 종료된다.
• 저장된 answer를 출력해준다. 

 

고찰

이분 탐색에 대해서 알아보았다. 이분 탐색 방법에 대해서 알고 있었지만, 어떻게 활용해야할지 문제에서 어떻게 적용해야 할지 이번 문제를 통해 잘 알 수 있었다. count가 가장 중요한 포인트였던거 같다.