Programmers - 입국심사

---

title: Programmers - 입국심사
date: 2022-07-26
tags:

• Algorithm
• Parametric Search

---

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

문제 요약

n명이 입국 심사를 한다. 각 심사대는 심사 시간이 다르며, 비어 있는 심사대에 가지 않아도 된다.
모든 사람이 심사를 받을 때, 가장 적게 걸리는 시간을 return한다.

문제 풀이

10M명, 10M 시간까지 주어진다. 인원이 너무 많으며, 남은 인원의 수와 각 심사대의 상황에 따라 배치가 다를 수 있다.
한 명씩 판단하는 것 보다 각 심사대를 기준으로 판단하는 것이 훨씬 빠르다고 생각하였다.
주어진 시간을 조정하며, 각 시간동안 최대 몇 명의 인원을 심사할 수 있는지 확인하였다.


최대 시간의 경우 가장 짧은 심사 시간 * 인원수 이며, 이는 심사대의 시간인 times에서 최소 시간을 찾아야 한다.
times는 정렬이 되었는지 보장되지 않으며, 이 하나를 위하여 정렬하는 것 보다는 O(n)을 이용하여 최소값을 찾는 것이 더욱 빠르다고 판단하였다.
최소 시간 1, 최대 시간은 위에서 언급한 시간으로 설정하여 Parametric Search를 진행하였다.
주어진 시간동안 각 심사대가 심사 가능한 인원을 누적하며, 이 인원이 주어진 인원 n보다 크거나 같다면 정답일 수 있다.
answer에 저장한 후, Right 값을 낮추며 더욱 빠른 시간에 판단 가능한지 확인한다.


이와 비슷한 문제가 현업에서 발생할 수 있다.
여러 Data 파이프라인의 처리 속도가 다르며, 처리 속도는 고정이라고 가정하자.
Data가 어느 타이밍에는 하루 처리량의 50%가 밀려올 수도 있고, 전체적인 시간대에 분산되어 처리를 할 수도 있다.
이 경우 처리 속도가 다르므로 Data의 개수에 따라 어느 파이프라인에서 처리할지 배치하는 알고리즘을 작성해야 할 수 있다.
Data가 계속하여 들어올 수 있으므로 과거에 몇 개의 Data가 넘어왔는지로 Data의 양을 예측해야 할 수 있다.
이러한 작업들을 통해 처리 비용 최적화를 진행할 수 있다.

프로그램

#include <vector>
#include <algorithm>

using std :: vector ;

long long solution ( int n , vector < int > times )
{
    long long answer = 0 ;
    long long llLeft = 1 ;
    long long llRight ;



    llRight = ( * std :: min_element ( times.begin () , times.end () ) ) * ( long long ) n ;
    while ( llLeft <= llRight )
    {
        long long llMid = ( llLeft + llRight ) >> 1 ;
        int * ipTemp = times.data () ;
        int iTableSize = times.size () ;
        long long llTempCount = 0 ;



        for ( int i = 0 ; i < iTableSize ; ++i )
        {
            llTempCount += llMid / ( * ipTemp ++ ) ;
        }

        if ( llTempCount < n )
        {
            llLeft = llMid + 1 ;
        }
        else
        {
            llRight = llMid - 1 ;
            answer = llMid ;
        }
    }

    return answer ;
}