[c++] 프로그래머스 :: 입국심사 (문제 풀이, 코드, 이분 탐색)

입국심사

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

문제

문제 설명

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

입출력 예

n	times	return
6	[7, 10]	28

입출력 예 설명

가장 첫 두 사람은 바로 심사를 받으러 갑니다.

7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.

10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.

14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.

20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

출처

※ 공지 - 2019년 9월 4일 문제에 새로운 테스트 케이스를 추가하였습니다. 도움을 주신 weaver9651 님께 감사드립니다.

 

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    vector<pair<long long,long long>> time_vec;

    sort(times.begin(), times.end());

    // setting
    for(long long i=0; i<times.size(); i++){
        time_vec.push_back(make_pair(times[i],0));
    }

    // 한명씩 넣기
    while(n--){
        long long min_idx=0;
        for(int i=1; i<time_vec.size(); i++){ // 최솟값 구하기
            if(time_vec[i].first+ time_vec[i].second < time_vec[min_idx].first+ time_vec[min_idx].second)
                min_idx = i;
        }
        for(int i=0; i<time_vec.size(); i++){ // 시간이 지났음을 표시
            if(i!=min_idx)
                time_vec[i].second-=time_vec[min_idx].second;
            if(time_vec[i].second<0) // 대기 중인 심사대
                time_vec[i].second =0; // 0으로 초기화
        }
        answer+= time_vec[min_idx].second;
        time_vec[min_idx].second = time_vec[min_idx].first; // 들어간 곳의 현재 남은 시간 초기화
    }

    // 남은 시간 끝내기
    long long max_time = 0;
    for(int i=0; i<time_vec.size(); i++){ // 최댓값 구하기
        if(time_vec[i].second > max_time)
            max_time = time_vec[i].second;
    }
    answer+=max_time;

    return answer;
}

 

풀이

time_vec라는 벡터에 (원래 걸리는 시간, 현재 남은 시간)을 저장하면서 두 시간의 합이 최소인 데스크에 한 명씩 집어넣는 방법이다. 두 시간의 합이 최소라면 지금 데스크에 들어가야하는 사람이 일을 끝마치는 시각이 가장 빠르다는 의미이므로 이렇게 코드를 구현하였다. 모두 데스크에 들어간 후에는 끝마치는 시각이 가장 느린 사람을 기점으로 종료 시각을 측정한다.

 

채점 결과

ㅎㅎ.. 왜 안되는지 모르겠다. 시간 초과가 문제라면 위의 테스트 1,2,3은 맞아야하는데 그것도 틀렸다. 근데 또 9번은 통과 ㅇㅅㅇ..?

 

다른 사람의 풀이

이분 탐색이라는 카테고리를 보고서도 어떻게 이분 탐색을 이용해야하는지 감이 안왔는데, 이번 문제를 통해서 감을 좀 잡은 것 같다. 이 문제는 기억해둬야겠다!

다른 사람의 풀이를 보고 내 방식대로 코드를 정리해보았다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

unsigned long long solution(int n, vector<int> times) {
    unsigned long long answer = 1e18;

    sort(times.begin(), times.end());

    long long min = 1;
    long long max = 1e15;//(long long)times.back()*n; // 가장 느린 사람이 모두 심사

    while(min<=max){
        long long number=0;
        long long mid = (min+max)/2;
        for(int i=0; i<times.size(); i++) // 해당 시간동안 심사를 끝낼 수 있는 사람 수
            number+=(long long)mid/times[i];
        if(number<n)
            min = mid+1;
        else{
            // 가능하면
            if(mid<answer) // 가장 작은 수 찾기
                answer = mid;
            max = mid-1;
        }
    }

    return answer;
}

주의 할 점

return 값을 unsigned long long으로 하지 않으면 오버플로우가 발생하는지 절반 가량이 틀리게 나온다.