문제

시내 주차장은 1부터 N까지 번호가 매겨진 N개의 주차 공간을 가지고 있다. 이 주차장은 매일 아침 모든 주차 공간이 비어 있는 상태에서 영업을 시작하며, 하룻동안 다음과 같은 방식으로 운영된다. 차가 주차장에 도착하면, 주차장 관리인이 비어있는 주차 공간이 있는지를 검사한다. 만일 비어있는 공간이 없으면, 차량을 빈 공간이 생길 때까지 입구에서 기다리게 한다. 만일 빈 주차 공간이 하나만 있거나 또는 빈 주차 공간이 없다가 한 대의 차량이 주차장을 떠나면 곧바로 그 장소에 주차를 하게 한다. 만일 빈 주차 공간이 여러 곳이 있으면, 그 중 번호가 가장 작은 주차 공간에 주차하도록 한다. 만일 주차장에 여러 대의 차량이 도착하면, 일단 도착한 순서대로 입구의 대기장소에서 줄을 서서 기다려야 한다. 대기장소는 큐(queue)와 같이, 먼저 대기한 차량부터 주차한다.

주차료는 주차한 시간이 아닌 차량의 무게에 비례하는 방식으로 책정된다. 주차료는 차랑의 무게에다 주차 공간마다 따로 책정된 단위 무게당 요금을 곱한 가격이다.

주차장 관리원은 오늘 M대의 차량이 주차장을 이용할 것이라는 것을 알고 있다. 또한, 차량들이 들어오고 나가는 순서도 알고 있다.

주차 공간별 요금과 차량들의 무게와 출입 순서가 주어질 때, 오늘 하룻동안 주차장이 벌어들일 총 수입을 계산하는 프로그램을 작성하라.

코드

from collections import deque
n, m = map(int, input().split())
parkFee =dict()
parkAvailable = [(i+1) for i in range(n)]
usingPark = list()
carWeight = dict()
queue = deque()
carLocation = dict()
money = 0
for i in range(n):
    parkFee[i+1] = int(input())


for j in range(m):
    carWeight[j+1] = int(input())
    carLocation[j+1] = 0
idx =1
for a in range(2*m):
    car = int(input())
    if car > 0:
        if len(usingPark) != n:
            usingPark.append(min(parkAvailable))
            carLocation[car] = min(parkAvailable)
            money += carWeight[car]*parkFee[min(parkAvailable)]
            parkAvailable.remove(min(parkAvailable))
        else:
            queue.append(car)
    else:
        parkAvailable.append(carLocation[-car])
        usingPark.remove(carLocation[-car])
        carLocation[-car] = 0
        if queue:
            a = queue.popleft()
            usingPark.append(min(parkAvailable))
            carLocation[a] = min(parkAvailable)
            money += carWeight[a] * parkFee[min(parkAvailable)]
            parkAvailable.remove(min(parkAvailable))

print(money)

설명

알고리즘 분류가 큐로 들어가는 문제이지만 구현에 초점이 맞춰진 문제 같다. 문제에서 주어진 시나리오대로 구현하면 되는데 나는 차가 주차되는 주차장 위치와 주차장 위치에 따른 가격, 차의 무게들을 해시로 저장해서 입력받는 숫자에 대입해서 주차요금을 계산해서 누적합을 해주고 배열 두개를 선언해 하나는 빈 주차장 하나는 사용중인 주차장을 표시해서 주차, 출차시 서로 pop과 append를 해주었다.