[BOJ] 1406 : editor - travelbeeee

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

---

[ 알고리즘풀이 ]

배열을 이용해서 문제를 구현하면, 임의의 위치에 삭제와 삽입 연산을 진행하는 과정이 시간 복잡도가 O(n)으로 TL 에 걸리게 된다. 임의의 위치에 삭제와 삽입 연산을 자주 진행해야될 때는 자료구조 연결 리스트를 사용해야된다. C++에서는 연결 리스트와 유사하게 동작하는 list Library를 지원해주므로 list STL 을 이용해서 문제를 해결할 수 있다.

( C++ list STL 명령어 정리 : https://travelbeeee.tistory.com/260 )

#include<iostream>
#include<string>
#include<list>

using namespace std;
list<char> L;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int N;
	string temp;
	char a, b;

	cin >> temp >> N;
	for (int i = 0; i < temp.length(); i++)
		L.push_back(temp[i]);

	list<char>::iterator P = L.end();
	for (int i = 0; i < N; i++) {
		cin >> a;
		switch (a) {
		case 'L': {
			if (P != L.begin())
				P--;
			break;
		}
		case 'D': {
			if (P != L.end())
				P++;
			break;
		}
		case 'B': {
			if (P != L.begin())
				P = L.erase(--P);
			break;
		}
		case 'P': {
			cin >> b;
			L.insert(P, b);
		}
		}
	}
	for (P = L.begin(); P != L.end(); P++)
		cout << *P;
	return 0;
}

---