[C++] 백준 18115번: 카드 놓기

문제 링크

18115번: 카드 놓기

문제 요약

1부터 N까지의 카드가 섞어져 있다. 해당 카드들에 대해 다음의 동작들을 수행할 수 있다.
1. 제일 위의 카드 1장을 바닥에 내려놓는다.
2. 위에서 두 번째 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다.
3. 제일 밑에 있는 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다.
이 동작들을 일련으로 수행했을 때, 카드가 1부터 N까지 순서대로 놓이게 되었다. 동작이 순서대로 주어지면, 원래 카드의 순서가 어떻게 되어 있었는지 출력해야 한다.

접근 방법

덱에 1부터 N까지 순서대로 넣어준 다음에, 동작을 그대로 구현해서 시뮬레이션 해줍니다. 이때 동작 수행 과정에서 나오는 카드들을 새로운 벡터에 pair로 저장하는데, {(나온 카드), (N부터 1까지 순서대로)} 쌍으로 저장해줍니다. 이후에 벡터를 오름차순으로 정렬하고 pair의 second를 순서대로 출력해주면 됩니다.

알고리즘 분류는 덱이었지만 저는 리스트로 풀었습니다.

코드

#include <bits/stdc++.h>

using namespace std;
using std::sort;

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

	int n;
	cin >> n;

	list<int> ls;
	for (int i = 1; i <= n; i++)
		ls.push_back(i);

	vector<pair<int, int>> card;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;

		list<int>::iterator it = ls.begin();
		switch (num) {
		case 1:
			card.push_back({ *it, n - i });
			ls.erase(it);
			break;
		case 2:
			it++;
			card.push_back({ *it, n - i });
			ls.erase(it);
			break;
		case 3:
			card.push_back({ ls.back(), n - i });
			ls.pop_back();
		}
	}

	sort(card.begin(), card.end());

	for (auto& i : card)
		cout << i.second << ' ';
	return 0;
}