n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다. 모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다. 입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한 사항 1. 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다. 2. 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다. 3. 심사관은 1명 이상 100,000명 이하입니다.
문제 회고
💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지
최소로 걸리는 시간을 구하는 문제인데 제한 사항에 10억명을 어떻게 처리할 지 고민해야 합니다. DP와 이분 탐색, 투포인터 정도를 생각할 수 있고 이 문제에서는 이분 탐색으로 시간 복잡도를 통과할 수 있었습니다.
최소 시간은 1, 최대 시간은 가장 긴 심사시간 x 전체 대기 인원으로 설정하고 이분 탐색을 시작합니다.
중간 값을 기준으로 각 심사시간이 해당 값에서 처리할 수 있는 대기 인원을 계산하여 중간 값의 시간 내에 모든 심사관이 처리할 수 있는 총 사람 수를 구해줍니다.
해당 값이 전체 대기 인원보다 크거나 작을 경우에 따라 최적의 시간을 구할 때까지 이분 탐색을 진행합니다.
이 때 각각의 심사관의 처리 시간이 겹치는 경우가 발생할 수 있지만, 여기서 모든 심사관이 처리 가능한 수를 계산하는 이유는 주어진 시간 내에 모든 사람이 처리 될 수 있는지를 판별하기 위함입니다. 따라서 겹치는 시간은 고려하지 않아도 됩니다.
각각의 최대 처리 능력을 합산하여 전체 대기 인원보다 크다면 더 짧은 시간을 시도하고, 작다면 더 긴 시간을 시도하여 최소 시간을 구하는 것입니다.
💡 내가 해결한 방식은?
재귀를 이용한 풀이 (시간초과)
def solution(n, times):
# 모든 사람이 심사를 받는데 걸리는 시간을 최소화
# 입국 심사 기다리는 사람 최대 10억명
# n = 6, times = [7, 10]
# 1-7, 1-10, 8-14, 11-20, 15-21, 22-28 : 6명 심사 최소 시간 28분
def passport_control(n, times, curr_time):
if n <= 0:
return curr_time
min_total_time = float('inf')
for time in times:
remaining = n - (curr_time // time)
if remaining < 0 :
remaining = 0
min_total_time = min(min_total_time, passport_control(remaining, times, curr_time))
return min_total_time
return passport_control(n, times, 0)
이분 탐색을 이용한 풀이
def solution(n, times):
# 최소로 걸리는 시간과 최대로 걸리는 시간 설정
left, right = 1, max(times) * n
while left < right:
mid = (left + right) // 2
# mid 시간에 심사 가능한 총 심사 인원
total = sum(mid // time for time in times)
# 최적의 시간값을 구할 때까지 이분 탐색
if total >= n:
right = mid
else:
left = mid + 1
# 최소 값은 left 이므로 left 반환
return left
출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면 출발지점, 도착지점, 바위 간의 거리가 아래와 같습니다.
위에서 구한 거리의 최솟값 중에 가장 큰 값은 4입니다. 출발지점부터 도착지점까지의 거리 distance, 바위들이 있는 위치를 담은 배열 rocks, 제거할 바위의 수 n이 매개변수로 주어질 때, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성해주세요.
제한 사항 1. 도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하입니다. 2. 바위는 1개 이상 50,000개 이하가 있습니다. 3. n 은 1 이상 바위의 개수 이하입니다.
