[백준] 5464. 주차장

문제 링크 : https://www.acmicpc.net/problem/5464

# N: 주차 공간 개수, M: 총 차량 댓수
N, M = map(int, input().split())

# 각 주차 공간의 단위 요금표
cost_table = []
for _ in range(N):
     cost = int(input())
     cost_table.append(cost)

# 차량 번호별 차량의 무게. 1번부터 시작
cars_weight = [0]
for __ in range(M):
    weight = int(input())
    cars_weight.append(weight)

# 출력할 정답. 총 금액
answer = 0

# 주차 공간 생성. 0은 비어있다는 의미
space = [0 for _ in range(N)]

# 주차 공간이 부족하면 대기할 대기열
queue = []

# count: 현재 주차된 총 댓수.
# for를 통해 매번 비어있는지 확인해도 되지만
# 매번 전체 주차 공간을 탐색하면 비효율적임.
# count와 N이 동일하면 빈 공간이 없다고 판단할 수 있음.
count = 0

for i in range(2 * M):
    # car: 양수이면, 해당 번호의 차량 주차. 음수이면 해당 번호의 차량 출차
    car = int(input())
    # 주차하는 경우
    if car > 0:
        # space가 만차 상태이면
        if count == N:
            # 주차 대기
            queue.append(car)
        # space에 빈 공간이 있으면
        else:
            # 앞에서부터 빈 공간 확인하기
            for j in range(N):
                # 현재 공간이 비어있으면
                if space[j] == 0:
                    # 현재 공간에 주차
                    space[j] = car
                    # 주차했으므로 현재 총 주차된 차량 수 증가
                    count += 1
                    break
    # 출차하는 경우
    else:
        # 음수를 양수로 변환. car 차량을 출차하면 된다.
        car = car * -1
        # 아래는 주차된 공간에서 car 차량을 찾는 로직
        for j in range(N):
            # 현재 확인중인 공간에 car가 주차되어 있으면
            if space[j] == car:
                # cost_table[j]: j번째 공간의 단위 무게당 비용
                # space[j]: j번째 공간에 주차된 차량 번호
                # cars_weight[space[j]]: 차량의 무게
                # car_cost: 해당 차량이 내야할 요금(공간의 무게당 비용 * 차량의 무게)
                car_cost = cost_table[j] * cars_weight[space[j]]
                answer += car_cost
                # 원래 주차된 차량이 나갔으므로
                # 해당 자리를 빈자리로 만들거나 대기 차량을 주차시켜야 한다.
                # 대기차량이 있으면
                if queue:
                    # 해당 자리에 대기 차량을 주차시킨다.
                    space[j] = queue.pop(0)
                # 대기 차량이 없으면
                else:
                    # 해당 자리를 빈자리로 만든다.
                    space[j] = 0
                    # 차량이 나가기만 했으니 총 주차된 차량 댓수를 1 감소시킨다.
                    count -= 1

print(answer)