C++ / 백준 / 5464 / 주차

문제

 

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

5464번: 주차장

 

문제풀이

 

우선순위 큐, 큐를 이용하여 풀었다. 생각보다 고려해야 될 것이 있던 문제였다.

주차장 자리가 없을 때 차량이 들어오는 것도 고려해야 하고, 주차장 자리가 여러 개일 때도 고려해야 했다.

 

우선순위 큐 remain은 남은 주차장을 나타낸다.

남은 주차장은 번호가 작은 주차장이 우선순위큐의 top부분에 오게 된다. ({번호, 요금})

큐 waiting은 남은 주차장이 없어 대기를 하고 있는 차의 번호를 저장한다.

 

마지막 2*M의 입력에서 두 가지로 조건을 나눠봤다.

들어오는 차량, 나가는 차량으로 나누고,

나가는 차량 부분에서는 추가로 대기 중인 차량이 있다면 나가자마자 바로 그 자리에 차를 주차하도록 했다.

 

		if (car < 0) {
			car *= -1;
			answer += parking[car].second * weight[car];
			remain.push(parking[car]);
			if (!waiting.empty()) {
				car = waiting.front();
				waiting.pop();
				parking[car] = remain.top();
				remain.pop();
			}
		}

차의 번호가 음수일 때이다, 이때는 차량이 나간다는 의미이다.

차량이 나갈 때마다 요금을 정산한다.

차량이 나갔으므로 주차장에 남은 자리가 생긴다. 우선순위 큐에 남은 자리를 표시한다.

이때, 대기 중인 차량이 있다면, 바로 빈자리에 넣어준다.

 

		else if (car > 0) {
			if (remain.empty()) waiting.push(car);
			else {
				parking[car] = remain.top();
				remain.pop();
			}
		}

차의 번호가 양수일 때이다, 이때는 차량이 들어온다는 의미이다.

만약 빈자리가 없다면 대기 목록에 차의 번호를 입력한다.

빈자리가 있다면 가장 작은 번호의 주차장에 차량을 주차시킨다.

 

코드

#include <bits/stdc++.h>
#define pii pair<int, int> 
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N(0), M(0);
	cin >> N >> M;

	priority_queue<pii, vector<pii>, greater<pii>>remain;
	int fee(0);
	for (int idx = 0; idx < N; ++idx) {
		cin >> fee;
		remain.push({ idx,fee });
	}

	vector<int>weight(M + 1, 0);
	for (int idx = 1; idx <= M; ++idx) {
		cin >> weight[idx];
	}

	vector<pii>parking(M + 1);
	queue<int>waiting;
	int answer(0), car(0);

	for (int idx = 0; idx < 2 * M; ++idx) {
		cin >> car;
		if (car < 0) {
			car *= -1;
			answer += parking[car].second * weight[car];
			remain.push(parking[car]);
			if (!waiting.empty()) {
				car = waiting.front();
				waiting.pop();
				parking[car] = remain.top();
				remain.pop();
			}
		}
		else if (car > 0) {
			if (remain.empty()) waiting.push(car);
			else {
				parking[car] = remain.top();
				remain.pop();
			}
		}
	}
	cout << answer;
}