백준 #1406

* 사진 클릭하면 링크이동 *

---

문제 접근방법

나는 커서를 보자마자 LIST가 떠올랐다. 왜냐하면 일단 커서라고 직관적으로 힌트를 주기도 했고, 시간제한이 짧은 문제인데 삭제와 삽입을 상수 시간에 해줄 수 있는 자료구조가 LIST라고 생각했다. 크게 어려웠던 점이 없었지만 좀 헷갈렸던 부분은 문장에 마지막에 위치한다는 말을 보고 나는 리스트 마지막에 ' '를 넣어 공간을 추가로 만들었다. 하지만 LIST.END()를 자체가 {'a','b','c'}이면 'c'의 위치가 아닌 'c'의 다음의 위치라는 것을 뒤늦게 떠올렸다. 이것 외에는 크게 어려웠던 점이 없었기에 주석으로 코드 설명 후 마치겠다.

#include<iostream>
#include<list>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	list<char>editor;
	list<char>::iterator cursor;
	string str;
	cin >> str;
	for (auto& i : str) {
		editor.emplace_back(i); 
	}
	cursor = editor.end(); //문장의 맨뒤에 커서위치 시킨다
	int num;
	string cmd;
	cin >> num;
	while (num--) { 
		cin >> cmd;
		if (cmd == "L") {
			if (cursor != editor.begin()) { //커서가 맨 왼쪽이면 무시
				cursor--;
			}
		}
		else if (cmd == "D") {
			if (cursor != editor.end()) { //커서가 맨오른쪽이면 무시
				cursor++;
			}
		}
		else if (cmd == "B") {
			if (cursor != editor.begin()) {
				cursor--;
				cursor = editor.erase(cursor); //삭제하기전 커서의 위치그대로 설정

			}
		}
		else if (cmd == "P") {
			char new_char;
			cin >> new_char;
			editor.insert(cursor, new_char);
		}
	}
	for (auto& u : editor) {
		cout << u;
	}
}

---

시간복잡도: 처음 에디터에 문자를 삽입할때 O(n), 명령어의 숫자만큼 각 명령어처리O(1)를 해주므로 O(n), 마지막 에디터 출력시 O(n) 

->O(n)