문제 설명
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.
처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.
입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
- 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
- 심사관은 1명 이상 100,000명 이하입니다.
풀이
무턱대고 for 문돌려서 처리는 할수야 있겠지만, 제한사항을 보면 어마어마한 0들의 습격에 for문으로 도배를 해버리면 시간복잡도에 무조건 걸릴게 뻔했다. 그리고 이 문제가 이분탐색 카테고리에 있는만큼 이분탐색으로 처리를 하라는 문제였다.
근데, 이걸 어떻게 이분탐색으로 처리를 해야하는지 답도 안보였다. 그래서 이분의 블로그를 보고 접근 방식을 찾을 수 있었다.
[프로그래머스] 이진탐색 - 입국심사 / Python(wwlee94 님 블로그)
문제를 풀기 위해서는 최솟값, 최댓값 을 이용하여 범위를 좁혀가면서 답을 도출해야 했다.
이 문제에서 최솟값은 0 아니면 1 일테고, 최댓값은 가장 늦는 심사관이 다 처리했을 경우이다.
만일 심사관의 [7,10] 리스트로 존재하고 전체 심사를 기다리는 사람이 6 명이라고 했을 때, 6명이 모두 가장 오랜 시간이 걸리는 심사관 시간인 10분으로 계산을 했을경우 최대 60분이 나오는 것이다.
최소, 최대의 중간값인 mid가 n명을 심사할 수 있는지 아닌지를 확인해서 이분탐색을 진행하는 것이다.
- 만일 n명을 심사할 수 있으면, 답을 mid로 설정해주고 최댓값을 하나 빼준다.
- 만일 n명을 심사할 수 없으면, 최소 값을 하나 더해준다.
코드
def solution(n, times):
answer = 0
start = 0
end = max(times) * n
while start <= end:
mid = (start+end)//2
cnt = 0
for time in times:
cnt += mid//time
if cnt >= n:
break
if cnt >= n:
answer = mid
end = mid-1
elif cnt < n:
start = mid+1
return answer문제를 풀고 배운점
이분 탐색의 이론을 배우고 문제를 여러개 풀어봤었지만, 막상 이렇게 다른 형식으로 문제가 나오니 맥을 잡을수도 없이 무너졌다. 이분탐색이 필요하다는 것은 알았지만, 최소 최대를 어떤걸로 설정하고 이걸 어떻게 돌려야 답이 도출되는 것인지 감도 안잡혔다. 하지만 이 말은 즉,문제를 적게 풀었다는 방증이다. 이분탐색이라는 알고리즘을 가지고 이렇게 다양하게 문제를 낼 수 있다는 걸 항상 인지하고 문제를 많이 풀어봐야겠다.
