[백준]Baekjoon 1406(자료구조)

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

풀이

만약 시간제한이 없다면 간단하게 생각될 수 있는 문제이다. 

각 명령어에 따라 조건문을 작성하고 string혹은 배열을 이용하여 명령어를 실행하면서

커서를 밀고 당기면서 문자열을 계속 새롭게 만들면 되기 때문이다.

나 같은 경우 string과 substr명령어를 사용해서 문자열을 계속 재배치했는데 역시 

시간초과에 걸리고 말았다.

어떤 자료구조를 이용해서 이 문제를 효율적으로 풀어야할지 생각해내는 것이 이 문제의

핵심이다.

나는 stack자료구조를 썼는데 left스택과 right스택을 만들어 커서를 기준으로 왼쪽에 있으면

left 스택에, 오른쪽에 있으면 right스택에 문자들을 집어넣는다면 쉽게 풀 수 있다.

예를들어 ab|cd 와 같이 ab와 cd사이에 커서가 주어졌을 때

left배열에 ab, right스택에 cd를 넣어주면 되며 

커서를 왼쪽으로 당긴다면 left의 가장위에 있는것을 right스택에 집어넣고

오른쪽으로 당긴다면 right의 가장 위에 있는것을 left스택에 집어넣으면 된다. 

또한 만약 커서 왼쪽의 문자를 삭제한다고 할 때 left스택 가장위의 문자를 제거한다면 쉽게

이 명령을 수행할 수 있다.

혹시 코드구현에 막히는 부분이 존재한다면 밑의 코드를 참조하도록 하자.

※ 스택 말고도 c++의 list자료구조를 쓴다면 좀 더 쉽게 구현할 수 있으므로 이 방법도 사용하면

좋을 거라고 생각한다.

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main()
{
	stack<char> left;
	stack<char> right;

	char c;
	while ((c = getchar()) != '\n') {
		left.push(c);
	}
	
	int n;
	scanf("%d", &n);

	while (n--)
	{
		getchar(); //'\n' 없애주기
		char cmd = getchar();
		if (cmd == 'P') {
			getchar(); //공백문자 하나 받고
			char k = getchar();
			left.push(k);
		}
		else 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 (!left.empty())
			{
				left.pop();
			}
		}
	}

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

	while (!right.empty())
	{
		printf("%c", right.top());
		right.pop();
	}
	printf("\n");
}