취미로 코딩하기

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

이번에 볼 문제는 백준 27497번 문제인 알파벳 블록이다.
문제는 아래 링크를 확인하자.

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

이 문제는 문자를 원소로 갖는 선형 수열의 맨 앞과 맨 뒤에 자료를 빠르게 추가 및 제거할 것을 요구하고 있다. 이를 \(O(1)\)에 수행할 수 있는 자료구조로 덱(deque)이 있다. 덱을 이용해 시뮬레이션을 진행하자.

가장 나중에 추가된 블록이 무엇인지는 지금까지의 1번과 2번 쿼리를 스택(stack) 자료구조에 보관하는 것으로 쉽게 관리할 수 있다. 

구현할 때, stl의 빈 스택 또는 덱의 원소(front 또는 back)에 접근하려는 시도는 undefined behavior이므로 유의하자.

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

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

int N;
deque<char> ans;
deque<int> stk;

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

	cin >> N;
	while (N--) {
		int q; cin >> q;
		if (q == 1) cin >> ans.emplace_back(), stk.emplace_back(1);
		else if (q == 2) cin >> ans.emplace_front(), stk.emplace_back(2);
		else {
			if (!stk.empty()) {
				if (stk.back() == 1) ans.pop_back();
				else ans.pop_front();
				stk.pop_back();
			}
		}
	}

	if (ans.empty()) cout << 0;
	else {
		for (auto& l : ans) cout << l;
	}
}