[연결리스트 | 연습 문제] 1406번 : 에디터

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

1406번: 에디터

---

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

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

void insert(int addr, int num) {
	dat[unused] = num;
	pre[unused] = addr;
	nxt[unused] = nxt[addr];
	if (nxt[addr] != -1) pre[nxt[addr]] = unused;
	nxt[addr] = unused;
	unused++;
}

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

void traversal()
{
	int cur = nxt[0];
	while (cur != -1) {
		cout << dat[cur];
		cur = nxt[cur];
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	fill(pre, pre + MX, -1);
	fill(nxt, nxt + MX, -1);

	int cursor = 0;	 //현재 가리키고 있는 번지

	string s;
	cin >> s;

	for (auto c : s)
	{
		insert(cursor, c);
		cursor++;
	}
	int num;
	cin >> num;

	for (int i = 0; i < num; i++)
	{
		char a;
		cin >> a;
		if (a == 'P')
		{
			char add;
			cin >> add;
			insert(cursor, add);
			cursor = nxt[cursor];
		}
		else if (a == 'L' && pre[cursor] != -1)
			cursor = pre[cursor];
		else if (a == 'D' && nxt[cursor]!=-1)
			cursor = nxt[cursor];
		else if (a == 'B' && pre[cursor] != -1)
		{
			erase(cursor);
			cursor = pre[cursor];
		}
	}
	traversal();
}

처음 나혼자 풀 때는 예제 3번을 통과 못 함.

=> cursor를 배열 인덱스처럼 ++,-- 로만 계산해서 메모리 상 남아있는 삭제된 번지로 커서가 이동하고 해서 안된거 같음

 

수정 후 1) 커서 확인하는 출력문을 안지워서 출력 초과 뜸

 

수정 후 2) 런타임 에러 (OutOfBounds) 발생

=> 이유를 모르겠어서 if 조건문을 정답 코드로 다 바꿔봄

 

수정 수정 수정 후) 정답

MX의 크기가 문제에서 필요한 배열 크기보다 작아서 그런거였음