[ 백준 BOJ / c++ ] 1406번 에디터

문제 

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

 

문장 str이 주어지고, m개의 명령어를 수행한 이후의 str을 출력하는 문제이다.

명령어의 종류는 다음과 같다.

 

또한, 문제 마지막 줄에 시작시 명령어의 커서는 맨 뒤에 위치한다고 한다.

---

접근 방식

처음에는 string의 substr을 사용해 문장을 잘라 붙이는 방식으로 진행하였다. 하지만 문장의 크기와 명령어 개수의

제한이 커 시간 초과가 발생하였다.

#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
	/*
		문자열 길이가 s 일때, 커서의 길이는 s+1로 설정

		L : 커서 왼쪽

		D : 커서 오른쪽

		B : 0 ~ 커서위치 substr, 커서 위치 + 1 ~ s+1 까지 substr 이후 뒤에 부분 리턴

		P : 0 ~ 커서위치 substr + '$ + 커서 위치 + 1 ~ s+1 까지 substr 리턴
	*/

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	string str; cin >> str;
	vector<int> cursorv(str.size() + 1);

	int cursorindex = str.size();

	int n; cin >> n;

	char c;
	char input;

	while (n--)
	{
		cin >> input;
	
		if (input == 'L')
		{

			if (cursorindex == 0)
				continue;

			cursorindex--;
		}
		else if (input == 'D')
		{

			if (cursorindex == str.size())
				continue;

			cursorindex++;

		}
		else if (input == 'B')
		{
			if (cursorindex == 0)
				continue;

			string s1 = str.substr(0,cursorindex-1);
			string target = str.substr(cursorindex-1, cursorindex);
			string s2 = str.substr(cursorindex,str.size()+1);

			str = s1+s2;

			cursorindex--;
		}
		else {
			cin >> c;

			string s1 = str.substr(0, cursorindex);
			string s2 = str.substr(cursorindex, str.size() + 1);

			str = s1 + c +s2;
			cursorindex++;
		}
	}

	cout << str;

	return 0;
}

 

결과

 

 

두 번째 시도는 커서가 문장에 맨 뒤에서 시작한다는 것을 힌트로 잡아 스택을 활용하기로 하였다. 두 개의 스택을 만들어 top값을 옮기는 방향으로 설계를 하였다. 설계는 다음 과 같다.

 

1. 두 개의 스택 sss1, sss2를 만든다.

2. 스택 sss1에 문장 str의 문자를 하나하나 담는다.

3. n개의 명령어를 적용한다.

    3-1. 명령어 "L" 인 경우 : 스택 sss1의값을 스택 sss2 으로 이동 ( sss1 이 비워져 있으면 실행 x )

    3-2. 명령어 "D" 인 경우 : 스택 sss2의값을 스택 sss1 으로 이동 ( sss2 이 비워져 있으면 실행 x )

    3-3. 명령어 "B" 인 경우 : 스택 sss1 맨 위의 값 지움 ( sss1 이 비워져 있으면 실행 x )

    3-4. 명령어 "P" 인 경우 : 추가할 문자 c를 입력 받아 스택 sss1에 추가

4. 스택 sss1의 문자를 문자열로 변환

5. 스택 sss2의 문자를 문자열로 변환

6. 스택 sss1의 문자의 순서를 반대로 뒤집기( 스택은 후입선출이기 때문에 그대로 뽑으면 문장이 뒤집어짐 )

7. 출력

 

---

코드

#include <stdio.h>
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

int main()
{
	// 출력 및 입력이 많아, tie 설정
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 문장 및 명령어 개수 입력
	string str; cin >> str;
	int n; cin >> n;

	char c;
	char input;

	// 두 개의 스택 선언
	stack<char> sss1;
	stack<char> sss2;

	// 문장 -> 첫 번째 스택에 저장
	for (int i = 0; i < str.size(); ++i)
	{
		sss1.push(str.at(i));
	}

	// 명령어 처리 
	while (n--)
	{
		// 명령어 입력 받음
		cin >> input;

		if (input == 'L')
		{
			// 명령어 L 일때 -> 오른쪽 이동, 첫 번째 스택값을 두 번째 스택으로 이동
			if (sss1.empty())
				continue;

			sss2.push(sss1.top());
			sss1.pop();
		}
		else if (input == 'D')
		{
			// 명령어 D 일때 -> 오른쪽 이동, 두 번째 스택값을 첫 번째 스택으로 이동
			if (sss2.empty())
				continue;

			sss1.push(sss2.top());
			sss2.pop();

		}
		else if (input == 'B')
		{
			// 명령어 B 일때 -> 첫번째 스택 맨 위의 값 지움
			if (sss1.empty())
				continue;

			sss1.pop();
		}
		else {
			// 명령어 P 일때, 추가할 문자 c를 입력 받아 첫 번째 스택에 추가
			cin >> c;

			sss1.push(c);
		}

	}

	// 스택 -> 문장 변환 작업

	string ss1 = "";
	string ss2 = "";

	// 첫 번째 스택 -> 문자
	while (!sss1.empty())
	{
		ss1 += sss1.top();
		sss1.pop();
	}

	// 첫 번째 스택 문장 뒤집어줌
	reverse(ss1.begin(), ss1.end());

	// 두 번째 스택 -> 문장
	while (!sss2.empty())
	{
		ss2 += sss2.top();
		sss2.pop();
	}

	// 출력
	cout << ss1 + ss2;

	return 0;
}