[백준/파이썬] 17612 : 쇼핑몰

https://www.acmicpc.net/problem/17612

17612번: 쇼핑몰

문제 요약 : N명의 고객들이 줄을 서서 k개의 계산대를 이용한다. 이용하는 데에는 각 고객이 가지고 있는 물품의 개수만큼의 시간이 든다. 만약 두 고객이 동시에 계산을 끝냈다면, 가장 뒤에있는 계산대를 이용한 고객이 먼저 나갈 수 있다. 나간 고객들의 순서와 고객의 번호를 곱한 값을 모두 더하여 출력하라.

우선 순위 큐를 이용한 심화문제..!

우선 순위 큐에 대해 개념은 숙지했어도, 실제로 적용하려니 어려웠다.

이런 저런 문제를 풀면 어떻게 사용하는것이 효율적인지 감을 잡아야겠다.

 

시도 0)

사실 시도를 여러번 했으나, 코드를 싹다 뒤엎어서 남아있지 않다..

가장 애를 먹었던 부분은, 시간의 흐름을 어떻게 적용하는가 였다.

 

말도 안되는 시도도 했다.

그냥 물품의 개수에 무작정 N을 뺐다. 그런데, 답이 유사하게 나와서 비슷하게 풀고 있는게 맞다고..? 하고 이틀은 고민한것 같다.

결론은 아님

 

시도 1 )

시간의 흐름!을 잡았다.

나중에 들어오는 값에는 pop한 값의 시간을 더해서 넣어줬다. 이 생각을 하는데 까지 얼마나 오래걸렸는지,,😣

# 17612 : 쇼핑몰
import heapq

N,k = map(int,input().split(' '))   # N: 고객수 k: 계산대 수
answer = 0
cashier = []   # 시간, 계산대 번호, 고객번호
finish = []

for i in range(N):
    customer, things = map(int,input().split(' '))
    if len(cashier) < k :  # 계산대 안참 -> 처음
        heapq.heappush(cashier,[things,(i+1),customer])
    else :  # 계산대 참 -> 빼고 넣기
        time, nowCashier, outCustomer = heapq.heappop(cashier)
        heapq.heappush(cashier,[things+time,nowCashier,customer])
        finish.append(outCustomer)

while cashier :
    time, nowCashier, outCustomer = heapq.heappop(cashier)
    finish.append(outCustomer)

for j in range(N):
    answer += (j+1)*finish[j]

print(answer)

이렇게 하면 139007이 나온다.

문제점을 찾기위해서 finish를 출력해봤는데, 같은 시간일 경우 카트 수가 더 큰게 나가야하는데 그게 실행되고 있지 않은듯 했다.

 

 

풀이 )

힙을 두개를 사용한다. cashier와 finish

cashier : 현재 계산대의 상태 [ 시간, 계산대번호, 고객번호 ] 

finish : 끝나고 나간 고객들의 상태 [ 시간, -계산대번호, 고객번호 ]

 

시도2에서 계산대 번호가 큰 게 먼저 나가지 않았기 때문에 이를 고치기 위해 finish도 힙으로 만들어 준 다음, 계산대번호에 -를 준다. -값을 주는 이유는 최대힙으로만들기 위함!

 

풀이의 흐름은 이렇다.

1. 계산을 하려는 고객의 번호와 물품 개수를 받아온다.
2. 만일 계산대에 자리가 남아있다면(계산하러 온 고객의 차례가 k 이하) cashier로 바로 갈 수있다.
   1. 기다리지 않았기 때문에 시간은 0으로 넣어준다.
3. 만일 계산대에 자리가 없다면(계산하러 온 고객의 차례가 k 다음) cashier에 있는 고객이 전부 계산해야 계산할 수 있다.
   1. heappop을 하여 계산대에 자리가 생기면, 계산을 하러간다. 이때, 기다렸기 때문에 이전 고객의 시간을 더하여 넣어준다.
   2. 나가는 고객의 경우, 향후 같은 시간이 나올 수 있으므로 계산대 번호가 큰 숫자가 우선순위를 가질 수 있도록 계산대 번호에 -값을 붙여 finish에 넣어준다.
4. cashier에 남은 값들을 전부 finish에 넣어준다.
5. finish값들을 순서와 곱하여 answer를 구한다.

 

# 17612 : 쇼핑몰
import heapq
import sys
input = sys.stdin.readline

N,k = map(int,input().split(' '))   # N: 고객수 k: 계산대 수
answer = 0
cashier = []   # 시간, 계산대 번호, 고객번호
finish = []

for i in range(N):
    customer, things = map(int,input().split(' '))
    if len(cashier) < k :  # 계산대 자리 남음
        heapq.heappush(cashier,[things,(i+1),customer])
    else :  # 계산대 자리 없음
        time, nowCashier, outCustomer = heapq.heappop(cashier)
        heapq.heappush(cashier,[things+time,nowCashier, customer])
        heapq.heappush(finish,[time, -nowCashier, outCustomer])

while cashier :
    time, nowCashier, outCustomer = heapq.heappop(cashier)
    heapq.heappush(finish,[time, -nowCashier, outCustomer])

for j in range(N):
    tmp = heapq.heappop(finish)
    answer += tmp[2] * (j+1)

print(answer)