백준 1406번 : 에디터

문자열을 직접 insert하는 과정은 삽입 인덱스 뒤에 있는 문자열을 뒤로 한 칸씩 밀어야 하기 때문에 O(n)의 시간이 추가로 걸린다. 따라서 문자열을 시뮬레이션하는 방법이 아닌 다른 방법을 찾아야한다.

커서 왼쪽과 오른쪽의 문자를 저장하는 stack인 left와 right를 만들어서 문자 삽입 시 left에 push하면 문자열을 한 칸씩 뒤로 미루는 작업이 없기 때문에 빠르게 처리할 수 있다.

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

int main()
{
	string str;
	getline(cin, str);

	stack<char> left, right;
	for (char ch : str)
	{
		left.push(ch);
	}

	int N;
	scanf("%d", &N);
	cin.ignore();
	for (int i = 0; i < N; i++)
	{
		string params;
		getline(cin, params);

		int blankIndex = params.find(" ");
		string param1 = params.substr(0, blankIndex);

		if (param1.compare("L") == 0)
		{
			if (left.empty())
			{
				continue;
			}

			right.push(left.top());
			left.pop();
		}
		else if (param1.compare("D") == 0)
		{
			if (right.empty())
			{
				continue;
			}

			left.push(right.top());
			right.pop();
		}
		else if (param1.compare("B") == 0)
		{
			if (left.empty())
			{
				continue;
			}
			left.pop();
		}
		else if (param1.compare("P") == 0)
		{
			string param = params.substr(blankIndex + 1, params.length());
			for (char ch : param)
			{
				left.push(ch);
			}
		}
	}

	while (!left.empty())
	{
		char ch = left.top();
		left.pop();

		right.push(ch);
	}

	str = "";
	while (!right.empty())
	{
		char ch = right.top();
		right.pop();
		str += ch;
	}
	printf("%s", str.c_str());
	return 0;
}