1. 문제
문제 설명
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.
처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.
입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
- 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
- 심사관은 1명 이상 100,000명 이하입니다.
입출력 예
n times return
6 [7, 10] 28
입출력 예 설명
가장 첫 두 사람은 바로 심사를 받으러 갑니다.
7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.
10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.
14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.
20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.
2. 풀이과정
이분탐색
제목에서도 알 수 있지만 이 문제는 이분탐색을 활용하는 문제이다. 만약 이분탐색을 사용하지 않고 문제를 풀려고 한다면 for문을 활용하여 입국심사과정을 시뮬레이션 해서 문제를 풀 수 있을 것이다. 하지만 이 방법은 지나치게 시간이 오래 걸린다. 반면 이분탐색을 활용하면 이 문제를 간단하게 해결할 수 있다.
이분탐색을 활용하는데에 있어 핵심은 문제의 구조를 뒤집어 생각하는 것이다. 이 문제는 사람의 숫자가 주어졌을 때 걸리는 시간을 구하는 문제이다. 하지만 이 문제를 임의의 시간이 주어졌을 때 주어진 인원의 입국심사를 시간 안에 완료할 수 있는지 뒤집어 생각해본다면 이분탐색을 활용하여 이 문제를 해결할 수 있다.
여기서 핵심인 시간이 주어졌을 때 주어진 인원의 입국심사를 완료할 수 있는지는 다음과 같이 판별할 수 있다. 주어진 시간을 , 각 심사관이 한 사람을 심사하는데에 소요하는 시간을 , 전체인원을 이라 한다면,
이면 주어진 시간 내에 완료할 수 있음
위 식의 좌변은 심사대를 비워두지 않고 최대한 활용했을 때 시간 내에 심사할 수 있는 인원수이다. 따라서 해당 조건을 만족하는 경우 주어진 시간 내에 완료가능, 만족하지 못할 경우 주어진 시간 내에 완료 불가능이라고 볼 수 있다.
코드
위의 조건을 기준으로 이분탐색을 활용한 코드를 작성하면 다음과 같다.
def solution(n, times):
times.sort() ## times 정렬
left = 1
right = times[len(times)-1]*n ## 가장 시간 오래걸리는 경우는 가장 느린 심사관에게 모든 사람이 심사받았을 경우보다 작을 것
answer = right ## 초기값을 최대로 지정하고 업데이트 시 점점 줄여가는 형태
while left <= right: ## 등호가 포함되어야 아래 if문에서 answer 업데이트 됨
given = int((left+right)/2)
sum = 0
for time in times:
sum += int(given/time)
if sum >= n:
if answer > given:
answer = given
right = given - 1
else:
left = given + 1
return answer출처: 프로그래머스 코딩테스트 연습, 이분탐색, 입국심사 (https://programmers.co.kr/learn/courses/30/lessons/43238)
