プログラマー-入国審査

プログラマー-入国審査

https://programmers.co.kr/learn/courses/30/lessons/43238
最初は,二分探索ではなくdfs完探を行い,結果としてタイムアウトが発生した.もちろんです.nが10000000未満の場合、dfsがnが10000000である場合、2^10000000のタイムアウトが発生する.他の方法が見つからなかったので説明しました.この探索で近づくのは不思議だ.どうしてこのやり方が思いつかなかったのか...二分探索で近づくと,ある値を基準に範囲を縮小し,答えを出す.この問題では、標準は時間です.理由は、全ての人に審査を受けるのに要する時間の最高値であり、時間を基準としているからである.
あとは2つの部分に分けて、時間を基準に左が最大、右が最大です.左は1(n=1、レビュー時間1)、右は(最長レビュー時間)*nです.
中間値(left+right/2)を総審査時間に設定し、その時間内に何人が審査を受けているかを確認すればよい.レビュー可能人員がn未満の場合、すべてレビューできないため、淘汰されます.最高価格をmid+1に変更します.n以上の場合は、レビューできます.最小時間なので、答えを変更します.その後、最大値(right)をmid-1に更新すると、答えが得られます.

コード#コード#

def solution(n, times):
    ##시간으로 기준을 두었을 때 최소값을 초기값으로 설정
    ##n이 1이고, 심사 시간이 1분만 걸리는 심사관
    answer = 0
    left = 1
    #times가 정렬되어있어야 한다.
    #right는 최악의 시나리오 -> N명이 가장 오래걸리는 심사관에게 심사 받을 경우로 초기값을 설정
    right = max(times) * n
    while left <= right:
        #총 소요 시간
        mid = (left+right) //2
        #심사받을 수 있는 사람 수
        people_cnt =0
        for time in times:
            # mid시간 동안 심사 받을수 있는 사람 수
            people_cnt += mid//time
        #심사 받을수있는 사람의 수가 주어진 N보다 작으면 전부 심사받을 수 없으므로 최소시간을 갱신해준다.
        if people_cnt <n:
            left = mid+1
            continue
        #구한 만약 총 소요 시간이 현재 설정한 최악의 경우보다 작으면 최악의 경우를 갱신
        if mid <= right:
            answer = mid
        right = mid -1
    return answer