프로그래머스 입국심사

최악의 경우 심사를 가장 느리게 하는 곳에서 모든 사람이 심사 받는 경우다. max(times) x n

최대 시간(max(times) x n), 최소 시간(0)을 가지고 이분탐색을 하면서 중앙값을 찾는다.

입국 심사대를 돌면서 심사대당 주어진 시간 내에 몇명을 처리할 수 있는지 구한다.

처리할 수 있는 누적 인원이 n과 같을 때 일단 list에 삽입해놓는다.

주어진 시간 내에 n명을 초과해서 처리할 수 있고, 초과된 인원이 현재 심사대에서 주어진 시간 내에 처리할 수 있는 인원보다 작거나 같으면 list에 중앙값을 추가한다. (count와 n이 일치하지 않더라도 시간 내에 처리할 수 있는 시간인 경우를 포함시킴)

list에는 n명을 처리할 수 있는 시간들이 있는데 가장 작은 값이 답이다.

def solution(n, times):
    mn = 0
    mx = max(times) * n
    md_list = []
    while mn <= mx:
        count = 0
        md = (mx + mn) // 2
        for j in range(len(times)):
            count += (md // times[j])
            if count == n:
                md_list.append(md)
                mx = md - 1
                break
            elif count > n and (count - n) <= (md // times[j]):  # count가 n을 초과할 경우 count - n 이 md//times[j]보다 작거나 같으면 추가
                md_list.append(md)
                mx = md - 1
                break
        if count > n:
            mx = md - 1
        elif count < n:
            mn = md + 1
        else:
             continue
    return min(md_list)

 

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

코딩테스트 연습 - 입국심사 | 프로그래머스