[C++] 백준 5464번: 주차장

문제 링크

5464번: 주차장

문제 요약

N개의 주차 공간이 있는 주차장에 M대의 차량이 들어오고 나간다. 차량은 현재 주차가 가능한 공간 중 가장 번호가 빠른 주차 공간에 주차를 한다. 주차 요금은 차량의 무게와 주차 공간의 가격의 곱만큼 발생하게 된다. 차량이 들어왔을 때, 주차 공간이 없다면 차량은 자리가 날 때까지 순서대로 기다려야 한다.
각 주차 공간의 가격과 차량의 무게, 차량의 출입 순서가 주어지면 이 날의 주차 요금을 계산해야 한다.

접근 방법

단순 구현 문제였습니다. 차량의 무게와 주차 비용은 별도의 배열에 미리 저장해둡니다.

트리셋을 준비하고, 셋을 1부터 N까지의 수로 채웁니다. 이 셋은 여석이 있는 주차공간들을 저장하고 있습니다. 트리셋은 자동적으로 오름차순을 유지하기 때문에, 차량이 들어오면 셋의 첫번째 원소를 할당해주면 됩니다.

차량이 들어 왔을 때, 주차 공간이 없을 수 있기 때문에, 일단 큐에다가 번호를 저장합니다. 그리고 큐와 셋 둘 중 하나라도 empty가 아니라면 하나씩 할당을 해줍니다. 이때 요금을 계산해서 결과에 더해주면 됩니다. 차량을 주차한 위치는 해시맵에 저장을 해줍니다.

차량이 나가는 경우에는 해시맵에서 차량이 주차된 주차 공간의 번호를 찾아 다시 셋에 넣어주면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, m;
	cin >> n >> m;

	vector<int> r(n + 1), w(m + 1);
	for (int i = 1; i <= n; i++)
		cin >> r[i];
	for (int i = 1; i <= m; i++)
		cin >> w[i];

	set<int> s;
	for (int i = 1; i <= n; i++)
		s.insert(i);

	int ans = 0;
	unordered_map<int, int> pos;
	queue<int> q;
	for (int i = 0; i < 2 * m; i++) {
		int car;
		cin >> car;

		if (car > 0)
			q.push(car);
		else {
			s.insert(pos[-car]);
			pos.erase(-car);
		}

		while (!q.empty() && !s.empty()) {
			set<int>::iterator it = s.begin();
			pos[q.front()] = *it;
			ans += w[q.front()] * r[*it];
			s.erase(*it);
			q.pop();
		}
	}

	cout << ans << '\n';
	return 0;
}