[백준] [C/C++] 1406번 : 에디터

문제

입력

첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000)이 주어진다. 셋째 줄부터 M개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.

출력

첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다.

예제 입력 1

abcd
3
P x
L
P y

예제 출력 1

abcdyx

풀이

#include <iostream>
#include <stack>
#include <list>

using namespace std;
using std::cout;
using std::cin;

int main() {

	int num;
	string str;
	cin >> str;
	cin >> num;

	list <char> lt(str.begin(), str.end());
	auto cursor = lt.end();
	// list <char> :: iterator cursor = lt.end(); 이거를 auto로 줄여서 사용가능

	for (int i = 0; i < num; i++) {
		char temp;
		cin >> temp;

		if (temp == 'L') {
			if(cursor!=lt.begin()) cursor--;
		}
		else if (temp == 'D') {
			if(cursor!=lt.end()) cursor++;
		}
		else if (temp == 'B') {
			if (cursor != lt.begin()) cursor = lt.erase(--cursor); 
		}
		else if (temp == 'P') {
			char insertChar;
			cin >> insertChar;
			lt.insert(cursor, insertChar);
		}
	}

	for (auto i = lt.begin(); i != lt.end(); i++) {
		cout << *i;
	}

	return 0;
}

알고리즘 [ 접근방법 ]

백준 Stack 카테고리에 있던 문제라 Stack을 이용해 풀어보려 했지만 도저히 풀이가 생각나지 않아 Stack으로는 풀지 못했다. Stack 풀이를 찾아보니 Stack을 두개 만들어 상황에 따라 각각 push, pop을 해주는 풀이던데 별로 효율적으로 보이지 않았다.

그다음 생각한 풀이는 linked list를 사용해서 커서를 자유자재로 변경해주는 것이였는데 본인은 C를 평소에 자주 사용했던 터라 linked list를 구현하기 위해선 일일히 코딩을 해야했다.

근데 C++에는 list라는 STL라이브러리가 있다고해서 이를 활용해보았다.

아직 list가 익숙치 않아 풀이를 어느정도 참고했기 때문에 다른 list 문제들을 좀 더 풀어봐야 겠다.