[Programmersコード練習]入国審査[Level 3]

質問(ソース)-プログラマ

アルゴリズムテクニック

分探索
+検索値(所要時間)について二分検索

説明:

質問では、空いている審査台があれば、審査を受けることもできるし、より早く終わる審査台を待つこともでき、そこで審査を受けることもでき、ここに迷う必要はないと説明しています.
重要なのは、一人一人が審査を受けるのにかかる時間を最小限に抑えることだ.
この問題を解く方法で2つ考えた.
まず静音、つまり所要時間が分からないまま、直接探してみます.
しかし、ここには問題がある.
すなわち、より早く終了した審査隊があれば、そこで審査を受けるのを待つのと、勝手にがらんとした場所に入るのと、どちらがどの条件で最高価格を獲得するのに貢献したのか分からない.
(+時間が長すぎて、最大10億人が並んでいました…)
第二に、時間を指定して出発します.
このようにかかる時間をxとして指定すると、x時間内にレビューデスクを通過する人が最大何人いるかを決定できます.

times는 입국심사대의 심사관마다 심사하는 데 걸리는 시간이 담긴 배열이다.
m은 입국심사대의 총 개수다.
n은 기다리는 인원이다.

총 통과 인원 = SUM(int(x / times[i])), i = 0 ~ m-1 이다.

여기서 int(x / times[i])는 입국심사대 i에서 x시간동안 최대로 통과시킬 수 있는 인원이다.

今では2つ目の解題方法が2つに分かれています.

所要時間の最大値または最長値からx値を変更し続け、["合計通過人数"=n]を満たす最小x値を見つければよい.

の最高値を指定し、最安値で二分探索を行い、[「総通過人数」==n]を満たすたびに、答えを最高値に更新する.

1号は線形探索,O(m)XO(n),2号は二分探索,O(m)XO(log(n).
(O(m)は、合計通過人数=SUM(int(x/回[i])、i=0~m-1の所要時間)
したがって、単純計算では1番が100000 X 10000000回、2番が100000 X 30回なので、当然2番を選べばいいのです.

ソースコード

python

# 이 문제의 key point는 2개다.
# 1. 이분탐색
# 2. 구하는 대상을 이분탐색한다.
#    (구하는 값은 걸리는 시간 -> 걸리는 시간의 최솟값, 최댓값 구해서 그 사이를 이분탐색)

def find_max_time(n, times):
    max_time = -1
    
    for time in times:
        if max_time == -1 or max_time < time:
            max_time = time
    
    return max_time * n
    
def solution(n, times):   
    # 문제의 답이 될 수 있는 값 중 최솟값, 최댓값 구하기
    min_time = 1
    max_time = find_max_time(n, times)
    
    # 문제의 답이 최솟값이므로 갱신을 위해 최댓값으로 설정
    answer = max_time
    
    # 문제의 답(target)을 대상으로 최솟값 ~ 최댓값 사이를 이분 탐색
    while (min_time <= max_time):
        # 중앙 값(mid target) 구하기
        target = int((min_time + max_time)/2)
        
        # 현재 답 후보(mid target) 만큼 걸렸다고 가정했을 때,
        # 각 심사관은 몇명의 인원을 통과 시켰는지 구하고 누적합(sum_n) 구하기 
        sum_n = 0
        for time in times:
            sum_n += int(target / time)
        
        # 누적합(sum_n)과 원래의 인원(n)을 비교
        if sum_n >= n:
            if answer > target:
                answer = target
            max_time = target - 1
        elif sum_n < n:
            min_time = target + 1
    
      
    return answer

cpp

#include <string>
#include <vector>

using namespace std;

long long solution(int n, vector<int> times) {
    long long min_time = 1;
    long long max_time = 0;
    
    for (vector<int>::iterator it = times.begin(); it != times.end(); it++) {
        if (max_time < *it)
            max_time = *it;
    }
    max_time *= n;
    
    long long answer = max_time;
    
    while (min_time <= max_time) {
        long long target_time = (min_time + max_time) / 2;
        
        long long sum_n = 0;
        for (int time : times)
            sum_n += (target_time / time);
        
        if (sum_n >= n) {
            if (answer > target_time)
                answer = target_time;
            max_time = target_time - 1;
        }
        else
            min_time = target_time + 1;
    }
    
    return answer;
}

に感銘を与える

この人で探索すればいいと思いましたが、この時間(探索した値)で探索しようと思ったのは長い時間がかかりました.
やっぱり水門を開けるのが一番難しい….