[BOJ] 1406: 에디터

문제 링크 : 백준/BOJ https://www.acmicpc.net/problem/1406

1406번: 에디터

 

이게 스택으로 풀면 o(n+m)에 풀리는 문제임을 백준 인강을 보고서야 알았다.

스택은 비교적 간단한 자료구조이지만, 막상 활용되는 문제들을 보면 이 문제에 스택이 쓰인다고?? 할 만한 문제가 은근히 많은 것 같다. 물론 내 기준이다..

 

이 문제의 핵심은 커서를 기준으로 왼쪽, 오른쪽에 두 개의 스택을 두는 것이다.

맨 처음에는 커서가 문장의 맨 오른쪽에 있다 했으므로 왼쪽 스택에 전체 문자열을 차례로 쌓는다.

그리고 각 명령에 대해 알맞게 문자를 옮기면 된다. 즉, 커서는 가만히 두고 그 커서를 중심으로 문자를 옮기는 방식이다.

 

단, 스택의 LIFO 특성을 다시 상기시켜보자. left 스택을 그대로 pop하면 원하는 순서의 역순이 튀어나올 것이다. 그래서 그걸 그대로 right 스택에 옮겨 닮는 작업 또한 필요하다.

 

/*
1406번 - 에디터
*/
#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main() {
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	string s; int m; stack<char>left, right;
	cin >> s;
	cin >> m;
	
	//처음에는 커서가 문자열의 제일 오른쪽에 있으므로
	for (int i = 0; i < s.size(); ++i) {
		left.push(s[i]);
	}

	for (int i = 0; i < m; ++i) {
		char cmd;
		cin >> cmd;

		if (cmd == 'L') {
			if (!left.empty()) {
				right.push(left.top());
				left.pop();
			}
		}
		else if (cmd == 'D') {
			if (!right.empty()) {
				left.push(right.top());
				right.pop();
			}
		}
		else if (cmd == 'B') {
			if (!left.empty()) {
				left.pop();
			}
		}
		else {
			char c;
			cin >> c;
			left.push(c);
		}
	}

	while (!left.empty()) {
		right.push(left.top());
		left.pop();
	}

	while (!right.empty()) {
		cout << right.top();
		right.pop();
	}
}