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

임의의 위치에 삽입과 삭제가 잦은 경우, 시간복잡도 상의 이득을 위해

연결 리스트의 자료구조를 생각해보아야 한다

연결리스트는 양 끝을 제외하고는 이전 주소 값과 다음 주소 값을 가지는 노드를 가진 구조이다 

C++ 의 STL list 를 이용해서 풀면 상대적으로 구현이 편하다

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

1406번: 에디터

#include <bits/stdc++.h>
using namespace std;

int main(){
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	string start;
	list<char> li;
	int m;
	
	cin >> start;
	for (auto k : start)
	{
		li.push_back(k);
	}
	// 반복자 ::iterator 대신에 auto로 대체 가능하다 
	auto cursor = li.end();
	cin >> m;
	while (m--)
	{
		char cmd;
		cin >> cmd;
		
		if (cmd == 'L')
		{
			if (cursor != li.begin())
			{
				cursor--;
			}
		} 
		else if (cmd == 'D')
		{
			if (cursor != li.end())
			{
				cursor++;
			}
		}
		else if (cmd == 'B')
		{
			if (cursor != li.begin())
			{
				cursor--;
				//  erase 함수의 리턴 값은 다음 요소의 반복자이므로 
				cursor = li.erase(cursor);
			}
		}
		else // 'P'
		{
			char add;
			cin >> add;
			li.insert(cursor, add);
		}
	}
	for (auto k : li)
	{
		cout << k;
	}
	
	return 0;
}