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

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

1406번: 에디터

문제분석

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

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

이 편집기가 지원하는 명령어는 다음과 같다.

L	커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
D	커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
B	커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨) 삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
P $	$라는 문자를 커서 왼쪽에 추가함

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

​문제풀이

해당 문제는 리스트(자세히 말하자면 더블 링크드 리스트) 또는 스택을 이용해 해결 가능한 문제이다.

이번 포스팅에서는 리스트를 이용해 풀어보겠다!

​

시간제한이 있는 문제이므로 혹시 모르니 입출력 속도를 높여주고,

1. 리스트를 하나 선언하여 string의 값을 리스트에 넣어준다.

-> 이 코드는 list<char> li(s.begin(),s.end()); 와 같이 표현가능하다!

​

2. 반복자를 하나 생성하여 해당 리스트의 맨 뒤를 가리키게 한다.

-> 굳이 iterator선언 없이 auto 키워드를 이용해 생성가능하다.

-> 참고로 end()는 리스트의 맨 마지막을 가리키는 것이 아니라, 맨 마지막의 다음을 가리키고 있다고 한다!

​

3. P 명령일 땐, 단어 하나를 더 입력받아 현재 커서(=iter)가 end()일 경우 맨 뒤에 위치하고 있음을 뜻하므로 push_back해준다.

그렇지 않으면 해당 커서의 위치에 추가한다.

(리스트는 해당 iter가 가리키는 위치에 추가하면, 그 위치 뒤에 오는 모든 요소를 뒤로 밀어버리고 생기는 빈 공간에 요소를 추가한다. = 왼쪽에 추가!)

​

※ 리스트에 {'A', 'B', 'C'}가 있다고 하자 (편의상 대충 표기함)

현재 iter가 B를 가리키고 있다고 할 때, li.insert(iter, 'ㅋ'); 을 실행하면

{'A', 'ㅋ', 'B', 'C'} 이렇게 iterator의 왼쪽에 요소를 추가하고 여전히 iterator는 'B'를 가리킨다!

​

4. L 명령일 땐, 리스트의 begin()이 아니라면 iter를 감소시킨다.

​

5. D 명령일 땐, 리스트의 end()가 아니라면 iter를 증가시킨다.

​

6. B 명령일 땐,

• 커서가 현재 맨 오른쪽이면 pop_back해준다.
• 맨 앞이면 무시한다.
• 맨 앞, 뒤가 아니라면, iter를 감소시키고 erase 해준다.

​

※ erase는 삭제를 수행한 이후에 iterator를 반환한다. 따라서 반드시 반환되는 반복자를 받아서 저장하는 방식으로 구현해야한다!

​

※ 리스트에 {'A', 'B', 'C'}가 있다고 하자

iter는 현재 'B'를 가리키고 있는 상태에서 iter = li.erase(iter)를 실행하게 되면, {'A', 'C'}와 같은 상태가 되고, iterator는 B 뒤에 있던 C를 가리키게 된다.

따라서 커서 왼쪽의 값을 삭제하고 원래 가리키던 걸 가리키게 하려면 먼저 반복자를 하나 감소시킨 뒤, 삭제를 진행해야한다!

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

using namespace std;

list<char> li;
list<char>::iterator iter ; //반복자 선언

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

	string s;
	char instruction, ch;
	int n;

	cin >> s >> n;

	for (int i = 0; i < s.length(); i++) {
		li.push_back(s[i]);
	}
	iter = li.end();

	while (n--) {
		cin >> instruction;
		if (instruction == 'P') {
			cin >> ch;
			if (iter == li.end()) { // 맨 뒤면 맨 뒤에 삽입
				li.push_back(ch);
				iter = li.end();
			}
			else { // 아니면 중간에 삽입
				li.insert(iter, ch);
				//iter++;
			}
			
		}
		else if (instruction == 'L') { // 맨 앞 아니면 커서 왼쪽으로 이동시킴
			if (iter != li.begin()) {
				iter--;
			}
		}
		else if (instruction == 'D') { // 맨 뒤 아니면 커서 오른쪽으로 이동시킴
			if (iter != li.end()) {
				iter++;
			}
		}
		else if (instruction == 'B') {
			if (iter == li.end()) { // 커서가 맨 오른쪽이면 맨 뒤 삭제
				li.pop_back();
				// iter = li.end();
			}
			else if (iter == li.begin()) { // 커서가 맨 앞이면 무시
				continue;
			}
			else { // 맨 앞, 맨 뒤 모두 아니면 커서 왼쪽의 문자 삭제
				iter--;
				iter = li.erase(iter);
			}
		}
	}
	for (iter = li.begin(); iter != li.end(); iter++) {
		cout << *iter;
	}
    return 0;
}