프로그래머스 (입국심사, 이분탐색) C++

 

n 명의 사람들이 times 배열의 크기만큼의 입국 심사를 가장 빨리 통과할 수 있는 알고리즘을 작성하는 문제이다. 보자마자 while 문 안에서 sec를 하나씩 증가해주고 카운트를 해주면서 마지막 한 명이 남았을 때 어느 입국 심사대를 통과해야 가장 짧은 시간이 나올 수 있는지 찾을 수 있다고 생각해서 코드를 작성해보았다.

 

다음은 테스트 케이스 하나를 통과한 코드 작성이다.

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    int sec = 0;
    int sum = 0;
    long long min = 1000000001;
    int member = 0;
    vector<int> count(times.size(), 0);
    
    while(true) {
        if(member == n) break;
        
        
        for(int i = 0 ; i < times.size() ; i++) {
            if(sec % times[i] == 0) {
                count[i]++;  
                member++;
                if(member == n) {
                    for(int i = 0 ; i < times.size() ; i++) {
                        if(sec % times[i] != 0) {
                            if(min > (count[i]+1) * times[i]) {
                                min = (count[i]+1) * times[i]-1;
                            }
                        } else {
                            if(min > sec + times[i]) {
                                min = sec + times[i]-1;
                                sec--;
                            }
                        }
                    }
                    sec = min;
                }
            }
        }
        // cout << member << " ";
        sec++;   
    }
    
    answer = sec;
    
    return answer;
}

 

이분 탐색을 하지 않고 순차적으로 초가 증가함에 따라 누가 들어갈 수 있는 지를 고려했다. 하지만 이는 입국심사대의 개수가 3개 이상이 될 경우를 전체적으로 고려하지 못한 코드 작성이다. 좀 더 보편적으로 적용될 수 있는 코드를 작성해야 했다. 

 최적 시간을 이분 탐색으로 Max와 Min을 줄여나가면서 찾는 방법이 모든 경우의 수를 효율적으로 고려한 경우가 되겠다. 이 생각을 어떻게 해야 할까. 맨 처음 이 문제를 봤을 때 물어보는 것이 최단 시간이었고, 흠... 어떻게 접근할 지 아직 감이 안온다... 좀 더 문제를 풀어봐야 감이 올 것 같다..

 

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

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    
    // 입국 심사대의 시간 순서에 따라 오름차순으로 정렬을 한다.
    sort(times.begin(), times.end());

    // 제일 작은 시간 초
    long long min = 1;
    
    // 가장 오래 걸리는 경우는 제일 길게 걸리는 심사대에 n명이 가서 검사를 하는 경우
    long long max = n * (long long)times.back();

    // Binary Search 의 개념을 적용하여 교차되는 순간 while 문을 종료
    while (min <= max) {

        // 평균을 먼저 계산을 한다
        long long avg = (max + min) / 2;
        long long tmp = 0;

        // 각 심사대가 평균 시간 내에 처리할 수 있는 사람을 세서 모두 더해준다.
        for (int i = 0; i < times.size(); i++) {
            tmp += (avg / (long long) times[i]);
        }

        // 만약 처리할 수 있는 사람이 n명 보다 많거나 같으면 max를 avg보다 1초 작게 설정한다.
        if (tmp >= n) {
            max = avg - 1;
            answer = avg;
        }
        else min = avg + 1;
    }
    return answer;
}