계산대 [23]
문제 설명
- 어떤 대형마트에 N개의 계산대가 존재한다. K명의 고객이 계산을 위해 줄을 서서 기다리고 있는데, 각 캐셔의 역량에 따라서 계산 속도에 차이가 있다고 한다.
- 한 계산대에서는 한 명만 계산을 진행할 수 있으며, 대기 줄의 가장 앞의 고객은 비어 있는 계산대로 가서 계산을 진행할 수 있다. 하지만, 어떤 캐셔의 계산대가 비어 있더라도, 기다렸다가 더 빨리 끝나는 숙련된 캐셔 쪽에서 계산을 진행할 수도 있다.
- 모든 사람이 계산에 걸리는 시간을 최소로 하고 싶을 때, 줄 서 있는 K명의 계산이 끝나는 시간을 구하는 프로그램을 작성하시오
입력 조건
- 첫 줄에 계산대의 개수 N과 줄 서 있는 고객의 수 K가 주어진다. (1 <= N <= 100,000 , 1 <= K <= 1,000,000,000)
- 다음 줄에 계산대별로 계산에 걸리는 시간 𝑇𝑁이 공백을 두고 주어진다. (1 ≤ 𝑇𝑁 ≤ 1,000,000,000)
출력 조건
- 줄 서 있는 모든 고객이 계산을 마치는 시간의 최소값을 출력
test case
-
입력예시 6 7 19 12 2 7 6 16
-
출력 예시 10
해결방법
- 문제에서 원하는 것은 모든사람이 계산에 걸리는 시간을 최소로 하고싶다는 것이다. 따라서 탐색의 기준을 계산시간으로 설정해 탐색한다.
- 계산시간의 최소값은 0, 최대값은 가장 계산하는데 시간이 오래걸리는 캐셔가 모든인원을 다 처리하는 경우이다.
- 이진탐색을 위해 계산한 중간값의 시간동안 캐셔들이 계산 가능한 총 인원이 기다리는 사람보다 많으면 계산 시간을 줄이고, 작으면 계산시간을 늘리면서 탐색을 하면 된다.
- 이진탐색이 끝나고 left가 계산시간의 최소값이다.
Big-O 복잡도
각각의 탐색과정에서 탐색의 범위가 반으로 적어지는 이진탐색을 사용해 O(logn)의 시간이 걸리 는데, 이진탐색 안에서 cashier배열을 탐색하는 시간이 O(logm)(m=cashier 배열의 크기)의 시간이 걸리므로 O(logn) * O(logm)인 O(log(nm))의 시간이걸린다.
- 시간복잡도 O(log(nm))
solution
def solution(cashier,k):
left, right = 0, max(cashier) *k #right는 가장 최악의 경우(가장 오래걸리는 경우)
cashier.sort()
while left < right:
mid = (left + right) // 2 #이진탐색
count = 0
for time in cashier:
count += mid // time #빨리 계산하는 캐셔 순으로 심사처리
if count >= k: break
if count >= k: #mid 시간동안 계산한 인원이 기다리는 사람 k보다 크면
right = mid #mid 시간보다 같거나 작은 시간에 k를 모두 처리할수 있다는 것
else: #그렇지 않가면, mid 시간동안 k명을 모두 계산해줄수 없다는것
left = mid+1; #따라서 주어진 시간이 mid 더 많아야한다.
return left
N ,K= map(int, input().split(" "))
cashier = list(map(int, input().split(" ")))
print(solution(cashier,K))
코드 설명
- 이진탐색을 이용하여 찾는데 찾는 기준을 총 계산하는데 걸리는 시간으로 잡았다.
- 따라서 최소 left는 0, 최대 right는 가장 오래걸리는 경우인 제일 오래걸리는 캐셔가 k명 을 모두 처리하는 경우로 max(cashier) *k로 초기화 한다.
- 그리고 cashier배열을 정렬한다. => 이진탐색이 가능하려면 정렬되어있어야 한다.
- while left < right인 조건으로 이진탐색을 시작한다.
- mid는 left와 right의 중간 값으로 초기화 하고 탐색으로 mid시간동안 계산 가능한 인원수를 구한다. count은 계산 완료한 인원수를 나타내며, 0으로 초기화 한다.
- 빨리 계산하는 캐셔 순으로 mid의 시간동안 캐셔들이 처리가능한 인원을 count에 더 한다. count가 원하는 k인원보다 크거나 같아지면 count하던 것을 break한다. (더 이 상 카운트 해도 소용없기 때문)
- 만약 count(캐셔들이 주어진 시간동안 처리가능한 인원)이 계산을 기다리던 사람 k보 다 크면 mid보다 작거나 같은 시간동안 k명을 처리가능 하다는 것이므로 탐색의 최 대 right를 mid로 설정한다.
- 그렇지 않으면 주어진 시간 mid안에 k명을 모두 처리하지 못한다는 것이므로 탐색할 시간의 최소값 left를 mid+1로 설정한다.
- 이진 탐색이 끝난 후 left를 리턴한다. = 모든 사람이 계산하는데 걸리는 시간의 최소값
입국 심사 문제와 비슷하다. https://programmers.co.kr/learn/courses/30/lessons/43238
