[프로그래머스] 입국심사

알고리즘/프로그래머스

코슬 2022. 6. 6. 00:05

코딩테스트 - 이분탐색 - 입국심사 [Level3]

코딩테스트 연습 - 입국심사

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한

programmers.co.kr

이분탐색 문제입니다.

정답 시간의 범위를 생각하면

최솟값은 "1"

최댓값은 "가장 오래 걸리는 시간 X n명"

사이에 정답이 있습니다.

이제 최솟값과 최댓값의 중간값을 기준으로 해당 시간 때의 사람 수를 구해서

최소, 최대 시간을 중간값으로 이동하며 범위를 줄입니다.

1. 해당 시간에 사람이 더 많다?

최댓값을 중간값으로 해서 범위 줄이기

2. 해당 시간에 사람이 더 적다?

최솟값을 중간값으로 해서 범위 줄이기

이를 반복해서 최솟값이 최댓값을 넘어갈 때의 최솟값을 도출하면 됩니다.