[프로그래머스 고득점 kit] 입국심사 ( C++ )

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

프로그래머스

위의 문제에 대한 풀이입니다.

 

우선 처음 단순히 생각하면 1명 처리 -> 처리 시간 입력, ...... n명 처리 -> 처리 시간 입력으로

입국 심사 횟수 N을 기준으로 O(N) 짜리 풀이를 생각했다.  하지만 이럴 경우, 10억회의 연산 발생으로 시간초과가 난다.

(이 오답 풀이는 맨 아래에 첨부하겠다.)

 

따라서 O(N) 보다 빠른 풀이, 혹은 심사위원의 수 ( 10만 ) 으로 문제를 굴려야 하는데, 나는 더 빠른 풀이를 찾아서 풀었다.

우선, 일반적인 "입국 심사 횟수" 를 기준으로 두지 말고 "n명을 처리할 수 있는 종료 시간" 에 중점을 두었다.

 "n명을 처리할 수 있는 종료 시간" 은 최소 1분( 바로 종료 ) 으로 바로 구할 수 있지만, 최대 시간을 적절히 구하는 건 은근 헷갈린다.

나는 이 최대 시간을, 모든 심사위원이 가장 심사가 느린 심사위원의 속도로 심사한다는 가정으로 Upper Bound를 구했다.

이제 이 최소시간 ~ 최대 시간을 이진탐색을 통해 탐색하며, n명을 처리할 수 있는 최소 시간을 찾으면 된다.

최소~ 최대 시간 은 1 ~ ( n / 심사위원 수) * (가장 느린 심사위원의 심사시간) 으로, 이 구간의 길이가 N이 되어

O(logN) 으로 시간 초과를 해결했다.

 

처음에 시간으로 중심점을 잡기 망설여 졌던건, 만약 10억분이 걸리는 심사위원이 1명뿐일시, max 값이

10억*10억으로 잡히고, 이게 N 값으로 O(logN) 이 되어도 시간초과가 날 것 같은 느낌 때문이었다.

하지만, 생각보다 Log2 (N ) 은 엄청나게 수를 줄여준다.

 

엄청 줄어드는 시간 복잡도.

오히려 수가 크면 클수록 기하학적으로 줄어든다. 이 점을 간과하여 오래걸린 듯하다...

 

정답코드.

#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 min = 1, max = (n / times.size()) * ((long long)times.back());
    //최소 종료시간 1분, 최대 종료시간 = 모두 제일 오래걸리는 사람 속도일 떄로 추산,
    //제일 오래걸리는 심사원의 종료시간마다, 모든 심사위원은 테이블 비울 수 있다.
    //answer=1;
    while (min <= max) { //n명을 처리할 수 있는 가장 빠른(작은) 시간 이진탐색으로 찾기
        long long mid = (min + max) / 2;
        long long sum = 0;
        for (int i = 0; i < times.size(); i++) {
            sum += (mid / (long long)times[i]);//정해진 시간 동안 각 심사위원이 처리할 수 있는 사람 수.
        }
        if (sum >= n) {// 더 앞선 시간에서 n명을 처리 가능한가?
            max = mid - 1;
            answer = mid;
        }
        else min = mid + 1; //아직 n명을 처리 못한다.



    }

    return answer;
}

 

오답코드 ( 우선순위 큐를 통해 n명을 일일이 처리하는 O(N) )

#include <string>
#include <vector>
#include<queue>
#include<iostream>
using namespace std;
priority_queue<pair<long long, long long> > pq; //종료시간, 걸리는 시간
long long solution(int n, vector<int> times) {
    long long answer = 0;
    for (auto a : times) pq.push({ -a,-a });
    long long time = 0; //최초부터 경과시간.
    while (!pq.empty() && n > 0) { //종료가 가장 빠른( 종료시간이 가장 낮은) 것을 뺀다.

        long long end = -pq.top().first, len = -pq.top().second;
        pq.pop();
        n--;

        time = end;//가장 적게 남은 심사대의 종료시간 까지 시간 진행

        pq.push({ -(end + len),-len });//다음 종료는 이번 종료시간+걸리는 시간. 
    }

    return time;
}
//현재 시간:
// 들어간 시간, 걸리는 시간.


//7 +(10-7) ==10  
// (12,0), (14,0),(7,7),(10,10)

// 7,7  10,10
//