(c++)백준 1406번: 에디터

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

1406번: 에디터

 

[풀이]

처음엔 string의 erase, insert를 사용하여 풀어보았는데, 시간초과가 났다. erase와 insert의 시간복잡도가 string 길이가 N일 때 약 O(N)이 걸리기 때문에 시간이 초과된 것 같다.

 

string으로 푼 코드

#include <iostream>
#include <string>

using namespace std;

string str;
char Cmd;
string PushWord;
int Cursor;
int M;

void solution() {
	cin >> str;
	int EndofString = str.size();
	Cursor = EndofString;//처음에 문장의 맨 뒤에 위치
	cin >> M;
	while (M--) {
		cin >> Cmd;
		if (Cmd == 'L') {
			//커서가 문장 맨 앞이면 무시
			if (Cursor == 0)
				continue;
			Cursor--;
		}
		else if (Cmd == 'D') {
			//커서가 문장 맨 뒤이면 무시
			if (Cursor == EndofString)
				continue;
			Cursor++;
		}
		else if (Cmd == 'B') {
			if (Cursor == 0)
				continue;
			//커서 왼쪽에 있는 문자 삭제
			str.erase(Cursor - 1, 1);
			Cursor--;
			EndofString--;
		}
		else if (Cmd == 'P') {
			cin >> PushWord;
			//왼쪽에 문자 추가
			str.insert(Cursor, PushWord);
			Cursor++;
			EndofString++;
		}
	}
	cout << str << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	solution();
	return 0;
}

 

커서 왼쪽 글자들을 담아둔 스택과 오른쪽 글자들을 담아둔 스택 두가지를 만들어 사용하였다.

먼저 왼쪽 스택에 주어진 글자들을 모두 담아둔다.

1. 오른쪽 이동: 오른쪽 스택의 가장 위에 있는 글자를 빼서 왼쪽 스택으로 집어넣기

2. 왼쪽 이동: 왼쪽 스택의 가장 위에 있는 글자를 빼서 오른쪽 스택으로 집어넣기

3. 삭제: 왼쪽 스택 pop

4. 값 집어넣기: 왼쪽 스택 push $

 

stack으로 푼 코드

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

string s;
char Cmd, PushChar;
stack<char>Left, Right;//커서 왼쪽, 커서 오른쪽
int M;

void solution() {
	cin >> s;
	for (int i = 0; i < s.size(); i++) {
		Left.push(s[i]);
	}
	cin >> M;
	while (M--) {
		cin >> Cmd;
		if (Cmd == 'L') {
			//커서가 문장의 맨 앞 = 커서 왼쪽에 아무것도 없음
			if (Left.empty())
				continue;
			//왼쪽 마지막 글자 커서 오른쪽으로 옮기기
			Right.push(Left.top());
			Left.pop();
		}
		else if (Cmd == 'D') {
			//커서가 문장의 맨 뒤 = 커서 오른쪽에 아무것도 없음
			if (Right.empty())
				continue;
			//오른쪽 가장 첫번째 글자 커서 왼쪽으로 옮기기
			Left.push(Right.top());
			Right.pop();
		}
		else if (Cmd == 'B') {
			if (Left.empty())
				continue;
			Left.pop();
		}
		else if (Cmd == 'P') {
			cin >> PushChar;
			Left.push(PushChar);
		}
	}
	//왼쪽에 있는 글자들 top부터 Right로 옮기면 순서대로 출력 가능
	while(!Left.empty()) {
		Right.push(Left.top());
		Left.pop();
	}
	while(!Right.empty()) {
		cout << Right.top();
		Right.pop();
	}
}

int main() {
	solution();
	return 0;
}