[백준/알고리즘/python/java] 5464번 - 주차장

이미지를 누르면 문제 링크를 보실 수 있습니다.

이미지를 누르면 문제 링크를 보실 수 있습니다.

이미지를 누르면 문제 링크를 보실 수 있습니다.

이미지를 누르면 문제 링크를 보실 수 있습니다.

 차근차근 문제에서 주어진 로직을 풀어보면, 그다지 어렵지 않은 문제였다. 문제의 로직은 따로 설명하게 없을 정도로, 문제에서 주어진 대로 그대로 구현하면 다들 풀 수 있을 것이다.

 

처음 입력받는 N과 M은 각각 '주차장 공간의 수'와 '차량의 수'이다. 모든 차량은 한 번씩 주차장에 들어갔다가 나오므로 (차량의 수 *2) 만큼의 출입 순서를 입력받아야 했다.

 

우선 index오류를 막기 위해, '요금을 나타내는 리스트'와 '각 차량의 무게를 나타내는 리스트'를 

빈 리스트 [] 가 아닌 [0]으로 시작했다.

들어오는 출입 순서를 덱으로 큐화 시켰다. popleft()를 쓰기 위함이다. 이 출입리스트가 빌 때 까지, 계산을 반복한다.

 

이 문제에서 생각해야 할 관건은 크게 2가지만 생각해주면 됐다.

• 주차 가능한 공간과 불가능한 공간을 구분지어주되,  각 주차장 자리에 몇 번째 차량이 주차되어있는지를 알 수 있어야 한다. (나중에 해당 차량이 나올 때, 그 자리에 해당 차량을 없애고 새로운 차량으로 대체해야할 가능성의 존재 때문에)
• 주차장이 꽉 차서 못들어가는 차량이 있다면, 대기열에 넣어줘야 한다. ('-차량'의 입력이 들어오면, 해당 차량을 나가게 해주고 그 즉시 대기열의 우선 차량을 넣어줘야 하기 때문에)

위와 같은 경우를 생각해주면서, 문제에 있는대로 구현해준 코드는 아래와 같다.

import sys
input = sys.stdin.readline
from collections import deque


N, M = map(int,input().split()) # 주차 공간, 차량 수 
fare = [0]
for _ in range(N):
    fare.append(int(input())) # 주차공간 번호의 단위무게당 요금
weight = [0]
for _ in range(M):  # 차량 1~M 까지의 무게
    weight.append(int(input()))

enter_order = []
for _ in range(2*M):    # 차량이 들어오고 나가는 출입 리스트 
    enter_order.append(int(input()))

queue = deque(enter_order)
# 1번 자리 부터 N번자리 까지 주차가능한지의 여부와 차 번호를 나타내는 리스트
possible_lot = [[True,0] for _ in range(N+1)] 

answer = 0
wait_for = deque([]) # 주차 공간이 현재 꽉차있을 때 대기하는 차 리스트
while queue:
    car = queue.popleft()   
    wait_queue = True # 대기하는 차가 발생하는지 나타내는 변수
    if car > 0 :    # 차가 들어오는 경우
        for i in range(1,N+1):
            if possible_lot[i][0] == True : # 비어있으면 그 자리 주차
                answer += weight[car] * fare[i] # 그 차의 무게 * 주차공간별 요금
                possible_lot[i][1] = car # 주차장 자리 i번에는 car번째 차가 주차함
                possible_lot[i][0] = False # 해당 자리(i)는 주차 불가를 뜻하는 False로 변경                
                wait_queue = False	# 차가 대기하지 않고 바로 주차했으므로, wait_queue = False로 변경 
                break   
        if wait_queue:  # 대기하는 차가 발생했다면
            wait_for.append(car) # 대기열에 그 차를 넣어준다.
    else:   # 차가 나가는 경우
        car = -car # 음수의 car를 양수로 바꾸고
        for i in range(1,N+1):
            if possible_lot[i][1] == car :
                possible_lot[i][0] = True # 다시 해당 주차자리 주차 가능을 뜻하는 True로 변경
                if len(wait_for) != 0: # 대기열에 차가 있다면
                    car = wait_for.popleft() # 대기하는 앞순 차 들어가게 해준다.
                    possible_lot[i][0] = False # 해당 주차자리 채우고
                    possible_lot[i][1] = car # 해당 주차자리는 그 차가 차지
                    answer += weight[car] * fare[i] # 주차료 계산
                break
print(answer)