[백준] 1406번 에디터

www.acmicpc.net/problem/1406

1406번: 에디터

연결 리스트의 기본 개념을 물어보는 문제였다.

처음 공부할때 커서의 위치가 너무 헷갈려서 힘들었던 기억이 난다. 그래서 메모장을 연상하면서 이해하기 위해 노력했다.

결과적으로 커서가 가리키는 칸이 a이고 뒤의 칸이 b라면 a의 뒤에, 즉 a와 b사이에 커서가 존재한다. (a|b)

또한, 커서가 가르키는 칸에 값이 없다면(문자열 끝의 다음 커서 값) 그 칸 자체가 커서라 생각하면 위처럼 이해할 수 있다.

 

배열 cur, dat, pre, nxt의 모든 값을 -1로 초기화 시킨다.(이 문제는 문자열을 이용하므로 -1은 유의미한 값이 될 수 없다.)

cur	0	1	2	3	4	5	6	7	8
dat	-1	a	b	c	-1	-1	-1	-1	-1
pre	-1	0	1	2	-1	-1	-1	-1	-1
nxt	1	2	3	-1	-1	-1	-1	-1	-1

<표1 : 문자열 abc를 순서대로 입력>

 

문자의 입력과정

1. 커서(cur)의 초기 값은 1이다. (cur[0]은 오류 방지를 위한 에어백이라 이해할 수 있다.)

2. 문자의 입력과정은 언급했듯 메모장을 연상하면 쉽다.

 2-1. dat[cur] = a; 새로운 a라는 문자가 입력되면 cur가 가르키는 값의 dat값을 a로 초기화 시킨다.

 2-2. pre[cur] = cur - 1; 

 2-3. nxt[cur - 1] = cur;

 2-4. cur++;

3. 2. 의 과정에서 pre와 nxt값에 cur위치를 저장함을 통해 cur의 값이 주어졌을 때 앞뒤의 모든 문자들이 무엇인지 찾아

   갈 수 있다.

 

커서 왼쪽 한칸 옮기기

간단하게 cur-- 라고 생각할 수 있지만, 메모장이라 생각하면 초기상태(cur = 0)보다 cur는 앞으로 갈 수 없다.

따라서 cur == 0 일 때는 cur--를 수행할 수 없다. (cur = 0일 때 무조건 dat[0] = -1, pre[0] = -1이다.)

 

커서 오른쪽 옮기기

왼쪽과 반대로 생각할 수 있다. 문자열의 마지막 문자 끝에 커서가 존재하고 마지막 cur의 dat값은 항상 -1이다.

따라서 nxt[cur] == -1 일 경우 cur++을 수행할 수 없다.

 

cur	0	1	2	3	4	5	6	7	8
dat	-1	a	b	c	-1	-1	-1	-1	-1
pre	-1	0	1	1	-1	-1	-1	-1	-1
nxt	1	3	3	-1	-1	-1	-1	-1	-1

<표2 : 문자열 abc입력 -> cur == 2에서 BackSpace = ac 출력>

 

커서 왼쪽에 있는 문자를 삭제

커서의 위치만 정확하게 인지하고 있다면 위의 표를 통해 어렵지 않게 생각할 수 있다. 

1. <표1>에서 cur == 2라고 하고 BackSpace연산이 들어왔다고 하자.

2. 다시 메모장을 생각하면 'ac'가 표시될 것이다.

   이는 곧 nxt[pre[cur]]이 nxt[cur]라는 의미이다.

   또한 pre[nxt[cur]]이 pre[cur]라는 의미이다.

3. 물론 예외적으로 cur == 0이라면 앞의 과정은 수행할 수 없다.

cur	0	1	2	3	4	5	6	7	8
dat	-1	a	b	c	-1	-1	-1	-1	-1
pre	-1	0	1	1	-1	-1	-1	-1	-1
nxt	1	3	3	-1	-1	-1	-1	-1	-1

<표3 : 문자열 ab입력 -> cur == 1에서 c추가 = acb 출력>

 

커서 왼쪽에 문자 추가

연결리스트에서 dat값은 단 한번만 초기화 된다. (초기에 -1로 초기화하는 것 제외)

따라서 새로운 문자열이나 문자를 입력받기위해 dat가 마지막으로 쓰여진 위치를 len에 따로 저장한다.

(문자 하나 입력시마나 len++)

1. <표3>을 통해 이해해보자. len == 3일 것이고, cur == 1이라 하자.

2. 사용되지 않은 dat에 초기화 하기 위해 len++;

3. 이하는 문자열 입력과정과 동일하다.

dat[len] = 'c'; pre[len] = cur; nxt[len] = nxt[cur];

if (nxt[cur] != -1) pre[nxt[cur]] = len; // 커서 왼쪽에 문자 추가가 되기전에 오른쪽에 문자가 있었는지 확인

nxt[cur] = len;

cur = len;

 

마지막으로 위의 표와 메모장을 통해 정리를 해보자면, 메모장에서 지워진 문자는 <표2>의 b처럼 표에는 존재하지만 커서로 부터 앞뒤로 시작과 끝으로 따라갔을 때, b의 위치를 가르키지 않기 때문에 결과적으로 메모장에 표현되지 않는다. 

 

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

const int MX = 1000005;
int pre[MX], nxt[MX];
char dat[MX];
int unused = 1;

void Make_Double_Linked_List(string Inp) {
	fill(pre, pre + MX, -1);
	fill(nxt, nxt + MX, -1);
	for (int i = 0; i < Inp.length(); i++) {
		dat[unused] = Inp[i];		
		pre[unused] = unused - 1;
		nxt[unused - 1] = unused;
		unused++;
	}
}

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

void function_L(int& cur) {
	if (pre[cur] == -1)
		return;
	cur = pre[cur];
}
void function_D(int& cur) {
	if (nxt[cur] == -1)
		return;
	cur = nxt[cur];
}

void function_B(int& cur) {
	if (pre[cur] == -1)
		return;
	nxt[pre[cur]] = nxt[cur];
	if (nxt[cur] != -1) pre[nxt[cur]] = pre[cur];
	cur = pre[cur];
}

void function_P(int& cur, int& len) {
	char ch;
	cin >> ch;
	len++;
	dat[len] = ch;
	pre[len] = cur;
	nxt[len] = nxt[cur];
	
	if (nxt[cur] != -1) pre[nxt[cur]] = len;
	nxt[cur] = len;
	cur = len;
}

int main(void) {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	
	string Inp;
	int N, len, cur;
	
	cin >> Inp >> N;
	len = Inp.size();
	cur = len;

	Make_Double_Linked_List(Inp);

	for (int i = 0; i < N; i++) {
		char odr;
		cin >> odr;
		switch (odr) {
		case 'L':
			function_L(cur);
			break;
		case 'D':
			function_D(cur);
			break;
		case 'B':
			function_B(cur);
			break;
		case 'P':
			function_P(cur, len);
			break;
		}
	}

	traverse();
}