Baekjoon 1406 - 에디터

💫 문제

---

🫧 Example Input/Output

// IN
abcd // 초기 문자열 (영어 소문자, 최대 100,000 글자)
3 // m : 명령어 수 (1 <= m <= 500,000)
B // 커서 왼쪽 삭제 (커서는 처음에 문자열 맨 오른쪽에 위치해 있음)
P d // d 를 커서 왼쪽에 추가
P x // x 를 커서 왼쪽에 추가
L // 커서 왼쪽으로 이동
D // 커서 오른쪽으로 이동
L
P y

// OUT
abcdyx

💫 C++ 풀이

---

🫧 1. 야매 연결리스트

#include <iostream>
#include <algorithm>

using namespace std;

// 바킹독 센세의 야매 연결리스트
const int MAX = 1000005;
char dat[MAX];
int nxt[MAX], pre[MAX];
int unused = 1;

void insert(int addr, char newData)
{
	dat[unused] = newData;
	nxt[unused] = nxt[addr];
	pre[unused] = addr;

	nxt[addr] = unused;
	if (nxt[unused] != -1)
		pre[nxt[unused]] = unused;

	unused++;
}

void erase(int addr)
{
	nxt[pre[addr]] = nxt[addr];
	if (nxt[addr] != -1) pre[nxt[addr]] = pre[addr];
}

void traverse()
{
	int cur = nxt[0];
	while(cur != -1)
	{
		cout << dat[cur];
		cur = nxt[cur];
	}
	cout << '\n';
}

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

	fill(pre, pre + MAX, -1);
	fill(nxt, nxt + MAX, -1);

	string s;
	cin >> s;

	int cursor = 0;
	for (auto c : s)
	{
		insert(cursor, c);
		cursor = nxt[cursor];
	}

	int m;
	cin >> m;

	for (int i = 0; i < m; i++)
	{
		char command;
		cin >> command;

		if (command == 'L')
		{
			if (pre[cursor] != -1)
				cursor = pre[cursor];
		}
		else if (command == 'D')
		{
			if (nxt[cursor] != -1)
				cursor = nxt[cursor];
		}
		else if (command == 'B')
		{
			if (pre[cursor] == -1)
				continue;
			erase(cursor);
			cursor = pre[cursor];
		}
		else if (command == 'P')
		{
			cin >> command;
			insert(cursor, command);
			cursor = nxt[cursor];
		}
	}
	traverse();
}

🫧 2. STL list

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

using namespace std;

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

	list<char> l;

	string s;
	cin >> s;

	for (auto c : s)
		l.push_back(c);

	list<char>::iterator cursor = l.end();
	
	int m;
	cin >> m;

	for (int i = 0; i < m; i++)
	{
		char command;
		cin >> command;

		if (command == 'L')
		{
			if (cursor == l.begin())
				continue;
			cursor--;
		}
		else if (command == 'D')
		{
			if (cursor != l.end())
				cursor++;
		}
		else if (command == 'B')
		{
			if (cursor == l.begin())
				continue;
			cursor = l.erase(--cursor);
		}
		else if (command == 'P')
		{
			cin >> command;
			l.insert(cursor, command);
		}
	}

	for (auto c : l)
		cout << c;
}

💫 Memo

---

• 바킹독 센세의 강의 영상을 한 번 본 이후 풀기 시작
  • 야매 연결리스트는 Dummy Node가 가장 앞에 있고, STL list는 Dummy Node가 가장 뒤에 있다는 댓글을 봤었는데, 그게 힌트가 됐다.
  • 위 그림은 각 풀이 방법 별 커서 위치 (생각하기 쉽게 커서가 데이터 위에 위치하는걸로)
• 야매 연결리스트로 풀 때 버그로 잡는 게 너무 힘들었다.

• STL list로 먼저 푼 다음, 야매 연결리스트를 다시 풀기 시작하니 조금 수월했다.

• 다 풀고 바킹독 센세의 답안과 체크해보니 똑같이 풀어서 안심했다.

• @ TIME : 스택을 이용한 풀이