취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 18115번 문제인 카드 놓기이다.
문제는 아래 링크를 확인하자.

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

카드를 내려놓는 과정을 거꾸로 따라가면서 원래의 카드 뭉치를 구하자. 예를 들어 수현이가 기술을 사용한 순서를 거꾸로 따라가면서 1번 기술을 썼었다면 바닥에 놓인 가장 위의 카드를 카드 뭉치의 가장 위로 올리는 식으로 원래의 카드 뭉치를 구하자.

이 때 카드 상태를 deque 자료구조로 관리하면 카드를 한 장 돌려놓을 때마다 $O(1)$의 연산으로 이전 카드 뭉치를 나타낼 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <deque>
#include <vector>
using namespace std;

int N;
vector<int> vec;
deque<int> dq;

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

	cin >> N;
	for (int i = 0; i < N; i++) cin >> vec.emplace_back(i);

	for (int n = 1; n <= N; n++) {
		if (vec.back() == 1) dq.push_back(n);
		else if (vec.back() == 2) {
			int tmp = dq.back(); dq.pop_back();
			dq.push_back(n);
			dq.push_back(tmp);
		}
		else dq.push_front(n);

		vec.pop_back();
	}

	while (!dq.empty()) {
		cout << dq.back() << ' ';
		dq.pop_back();
	}
}