Level 3. 입국심사

입국심사 [이분탐색]

코딩테스트 연습 > 이분탐색 > 입국심사

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

문제 구상

• 입력: 입국심사를 기다리는 사람 수(n), 각 심사관이 한명을 심사하는데 걸리는 시간이 담긴 배열(times)
• 출력: 모든 사람이 심사를 받는데 걸리는 시간
• 구상:
  1. 이분탐색을 위해 최소시간, 최대시간을 설정합니다.
  2. 최소시간이 최대시간보다 작거나 같을 경우,
     1) 두 시간의 평균값을 계산합니다.
     2) 해당 시간동안 각 심사관이 처리할 수 있는 사람 수가 n 보다 크거나 같을 경우, for문을 종료합니다.
  3. 2번의 경우가 성립할 때, 답을 갱신하고, 최대시간을 줄여 위 과정을 반복합니다.
  4. 2번의 경우가 해당하지 않을 경우 최소시간을 늘려 위 과정을 반복합니다.

문제 풀이

# 입력값
n = 6 # 입국심사를 기다리는 사람 수
times = [7,10] # 각 심사관이 한명을 심사하는데 걸리는 시간이 담긴 배열
# 출력값: 모든 사람이 심사를 받는데 걸리는 시간
result = 0
# 문제 구상:
# 01. 가장 빨리 끝나는 시간과 늦게 끝나는 시간을 지정
t_min, t_max = 1, max(times)*n
# 02. 가장 빨리 끝나는 시간이 가장 늦게 끝나는 시간보다 작거나 같을 경우 while문을 반복
while t_min <= t_max:
    t_mid = (t_min+t_max)//2 #두 시간의 평균값을 기준으로
# 03.
    cnt = 0
    for t in times:
        cnt += (t_mid//t) # t_mid 시간동안 해당 심사관이 처리할 수 있는 인원 수 계산
        if cnt >= n: # 만약 cnt가 기다리는 사람 수 n 보다 크거나 같을 경우,
            break # for 문 종료
    if cnt >= n:
        t_max = t_mid-1 # t_max값을 갱신
        result = t_mid # result값 갱신
    else: # cnt가 기다리는 사람 수 보다 작을 경우,
        t_min = t_mid+1 # t_min값 갱신
result

전체 코드

def solution(n,times):
    t_min,t_max = 1,max(times)*n
    result = 0

    while t_min<=t_max:
        t_mid = (t_min+t_max)//2
        cnt = 0
        for t in times:
            cnt+=(t_mid//t)
            if cnt >= n:
                break
        if cnt >= n:
            t_max = t_mid-1
            result = t_mid
        else:
            t_min = t_mid+1
    return result

# Code test
solution(n=6, times =[7,10])