[백준 1406] 에디터 (C++)

문제 링크: www.acmicpc.net/problem/1406

1406번: 에디터

1. 주의할 점

- 시간제한이 엄격하여 substr로 하면 TLE 발생한다

- 커서를 기준으로 앞의 문장과 뒤의 문장을 따로 저장한다

 

2. 구현

- 커서를 기준으로 앞의 문장은 Deque에, 뒤는 Stack에 저장한다

- 초기에 커서는 입력받은 문자의 맨 뒤에 위치하므로 Deque에 문자열을 전부 넣는다

- 명령어가 L이 들어왔다면, 왼쪽으로 커서를 움직여야하므로 덱이 비어있지 않다면 맨 뒤의 원소 1개를 빼서 Stack에 넣는다

- 명령어 D가 들어왔다면, 오른쪽으로 커서를 움직여야하므로 스택이 비어있지 않다면 스택의 Top에 위치한 원소를 빼서 Deque에 넣는다

- 명령어 B가 들어왔다면, 커서 기준 왼쪽의 문자를 삭제해야 하므로 덱이 비어있지 않다면 맨뒤에 위치한 문자를 제거한다

- 명령어 P가 들어왔다면, 문자를 한개 더 입력받은 후 커서의 왼쪽에 삽입해야하므로 덱의 뒷부분에 추가한다

- 커서의 왼쪽에 해당하는 문자열인 덱과 오른쪽에 해당하는 스택을 합하여 출력시키도록 한다

 

#include <iostream>
#include <string>
#include <stack>
#include <queue>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	string str, result = "";
	int num;
	char c, c2, tp;
	cin >> str >> num;
	stack<char> r;
	deque<char> dq;
	for (int i = 0; i < str.size(); i++)
		dq.push_back(str[i]);
	for (int i = 0; i < num; i++) {
		cin >> c;
		if (c == 'L') {
			if (dq.empty()) continue;
			else {
				tp = dq[dq.size() - 1];
				dq.pop_back();
				r.push(tp);
			}
		}
		else if (c == 'D') {
			if (r.empty()) continue;
			else {
				tp = r.top();
				r.pop();
				dq.push_back(tp);
			}
		}
		else if (c == 'B') {
			if (dq.empty()) continue;
			else 	dq.pop_back();			
		}
		else {
			cin >> c2;
			dq.push_back(c2);
		}
	}
	for (int i = 0; i < dq.size(); i++)
		result += dq[i];
	while (!r.empty()) {
		result += r.top();
		r.pop();
	}

	cout << result;
	return 0;
}