[アルゴリズム]プログラマ-入国審査

4027 ワード
パイ にぶんたんさく アルゴリズム#アルゴリズム# コーディングテスト プログラマ テキストリンク

問題の説明


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

問題の解き方


この問題はこの探索を利用して解決した問題である.このような探索に何度も触れたことのない私にとって、このような探索対象にかかる時間だとは思わなかったので、近づくことができませんでした.
簡単に言えば、
  • 入国審査官nと各審査官審査時間times
  • では、最悪の場合(すべての審査員が最長の審査員と同じ時間を必要とすると仮定)を最大値にリセットし、最適な場合(すべての審査員が最小の審査員と同じ時間)は最小値
    • にリセットする.
  • 現在可能な時間に현재 체크하려는 시간 값/각 심사관의 심사 시간をすべて加算します.これは、現在のすべての審査官が処理できる入国審査員の総数と同じです.(以下、sumと略す)
  • に加算された値がnより大きい場合は、現在の時間値が最適値ではないことを示すため、現在の時間の半分の上流部分を再検索し、小さい場合は反対部分を検索する.

    • どうして難しいの?


    簡単な二分探索でsum == nなら直接質問に答えればいいと思っていたのですが・・・問題で示した例n=6, times=[7, 10]について、値が29の場合、sum == nが満たされる.サンプル入力では選択されていませんが、テストケースでは頻繁に失敗し、多くのブログの参照後にエラーが見つかりました.

    破壊法(言うまでもなく)

    sum < nなら時間が足りないに違いないので増やすべきですが、逆にsum == nでもベストではない場合があるので、答えを記録してから範囲を絞って探索します.この探索の探索条件が終わったら,答えを出力すればよい.
    def solution(n, times):
    answer = []

    start, end = n * min(times) // len(times), n * max(times) // len(times)
    mid = (start + end) // 2

    while start <= end:
        sum = 0
        mid = (start + end) // 2
        for time in times:
            sum += mid // time

        if sum < n:
            start = mid + 1
        else:
            answer = mid
            end = mid - 1

    return answer

    TIL

  • 分の検索結果は必ずしも最適ではない可能性があります.
  • という探索自体を正確に理解する必要があるようだ.
    • これらのツールでより生産的である!🌻 あなたのための私の7月のピック
    gitlabインストール、構成