(C++) 백준 1406번 - 에디터

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

문제

> 한 줄로 된 간단한 에디터를 구현하려고 한다. 
> 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.

> 이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 
> 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.

> 이 편집기가 지원하는 명령어는 다음과 같다.
L - 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
D - 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
B - 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨)
    삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
P $ - $라는 문자를 커서 왼쪽에 추가함

> 초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 
> 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 
> 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.

접근

연결리스트를 사용해 구현해준다. 문제의 커서는 iterator형으로 리스트의 인덱스로 사용한다.
문제에 주어진 입력별 연산을 구현해주며 각각의 조건들을 유의한다.
B에대해서는 커서가 움직이는것이 아닌 커서의 왼쪽 값만 없애는 것이므로 이를 커서의 값이 변하지 안도록 값을 복사해 처리해준다.

문제해결

> 연결리스트를 사용해 입력받은 문자들에대해 문제에서 정의해준 명령을 구현해 처리한다.
> 문자형 연결리스트 editor를 만들고 입력받은 문자열에대해 반복문으로 문자들로 쪼개 리스트에 넣어준다.
> 커서를 이 리스트의 마지막인 editor.end()로 잡아주고 명령들을 처리한다.
> 문제에 주어진대로 L은 커서(cur)가 맨 앞인지 D는 맨 위인지 각각 보고 아니라면 커서에 증감연산자로 위치를 조정해준다.
> B는 맨앞인지 확인하고 아니라면 커서의 왼쪽에있는 값을 지워야하므로 임시변수로 커서값을 복사해와 감소연산자로 왼쪽에있는 값에 erase해준다. 
> 이는 실제로 cur의 값이 변하지 않는다는 것을 나타내기 위해 임시변수에 복사해 사용하는것이다.
> P는 스트링스트림으로 짤라내 받은 문자 c에대해 cur위치에 insert해준다. 
> insert는 자동으로 cur이 가리키는 문자 앞에 삽입해주기 때문에 별다른 처리를 하지않는다.
> 최종적으로 editor리스트에 있는 원소들을 출력한다.

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <list>
using namespace std;

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

	list<char> editor;

	string str, s;
	cin >> str;
	for (int i = 0; i < str.size(); i++) editor.push_back(str[i]);

	int M;
	cin >> M;
	cin.ignore();

	list<char>::iterator cur = editor.end();

	while (M--)
	{
		char command, c;
		getline(cin, s);
		stringstream ss(s);
		ss >> command;
		ss >> c;

		if (command == 'L')
		{
			if (cur == editor.begin()) continue;
			cur--;
		}
		else if (command == 'D')
		{
			if (cur == editor.end()) continue;
			cur++;
		}
		else if (command == 'B')
		{
			if (cur == editor.begin()) continue;
			auto a = cur;
			--a;
			editor.erase(a);
		}
		else if (command == 'P')
		{
			editor.insert(cur, c);
		}
	}
	for (auto& a : editor) cout << a;
}

후기

문제 태그에 연결리스트가 있길래 연결리스트가 무엇인지 알아보고 연결리스트로 구현해봤다.
그냥 배열로 해도 될거같은데 어떤 장단점이 있는지 자세히 알아봐야겠다.