<백준> 1406 에디터

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

 

이 문제도 링크드리스트 구현 못해서 미뤄놨는데 생각보다 조건이 많았음.

예외조건 먼저 설계하고 구현하는 게 더 효율적일 듯싶다.

그냥 막 들어갔다가 3시간 넘게 걸림.

#include<iostream>
#include<string>

using namespace std;

class Node
{
public:
	char data;
	Node* prev;
	Node* next;
	bool left;
	Node(char c)
	{
		data = c;
		next = prev = nullptr;
		left = false;
	}
};

class list
{
public:
	Node* head;
	Node* tail;
	Node* cursor;
	list()
	{
		head = tail = cursor = nullptr;
	}
	void init(char c)
	{
		Node* temp = new Node(c);
		if (head == nullptr)
		{
			head = tail = cursor = temp;
			return;
		}
		temp->prev = cursor;
		cursor->next = temp;
		cursor = temp;
	}
	void left()
	{
		if (cursor == head)
			return;
		if (cursor == tail && !cursor->left)
		{
			cursor->left = true;
			return;
		}
		cursor->left = false;
		cursor = cursor->prev;
		cursor->left = true;
	}
	void right()
	{
		if (cursor == tail)
		{
			if (cursor->left)
			{
				cursor->left = false;
				return;
			}
			else
				return;
		}
		cursor->left = false;
		cursor = cursor->next;
		cursor->left = true;
	}
	void back()
	{
		if (cursor == head)	//head 앞 쪽 => 예외처리;
			return;
		if (cursor->prev == head)	//head 뒤 쪽 == head 변화;
		{
			cursor->prev->next = 0;
			head = cursor;
		}
		else if (cursor == tail && !tail->left) //tail 뒤 쪽 == tail 변화;
		{
			cursor = tail->prev;
			tail = cursor;
			cursor->left = false;
		}
		else
		{
			cursor->prev->prev->next = cursor;
			cursor->prev = cursor->prev->prev;
		}
	}
	void push(char c)
	{
		Node* temp = new Node(c);
		if (cursor == head)	//head 앞 쪽 == head 변화;
		{
			temp->next = cursor;
			cursor->prev = temp;
			head = temp;
		}
		else if (cursor==tail && !tail->left)	//tail 뒤 쪽 == tail 변화;
		{
			temp->prev = cursor;
			cursor->next = temp;
			temp->left = false;
			cursor = temp;
			tail = temp;
		}
		else
		{
			cursor->prev->next = temp;
			temp->prev = cursor->prev;
			cursor->prev = temp;
			temp->next = cursor;
		}
	}
};

int N;

int main()
{
	list l = list();
	char c;
	string s;
	cin >> s;
	cin >> N;
	for (int i = 0; i < s.size(); i++)
	{
		l.init(s[i]);
	}
	l.tail = l.cursor;
	for (int i = 0; i < N; i++)
	{
		cin >> c;
		if (c == 'L')
			l.left();
		else if (c == 'D')
			l.right();
		else if (c == 'B')
			l.back();
		else
		{
			cin >> c;
			l.push(c);
		}
	}
	Node* n = l.head;
	while (1)
	{
		cout << n->data;
		n = n->next;
		if (n == 0)
			break;
	}
	return 0;
}

모든 조건이 왼쪽에서 push 혹은 back 하라고 되어있기 때문에 노드 멤버 변수를 left 하나 더 잡았음.

쉽게 말해서 tail을 제외하면 노드 cursor가 가리키는 노드의 앞 쪽에 커서가 위치한다.

tail의 경우 노드가 tail일 때 left==true이면 tail 앞 쪽 커서, left==false이면 tail 뒤 쪽 커서로 생각하면 된다.

B 입력받았을 때 예외 조건 세 가지 head의 앞 쪽 커서, head의 뒤 쪽 커서, tail의 뒤 쪽 커서

P 입력 받았을 때 예외 조건 두 가지 head의 앞 쪽 커서, tail의 뒤 쪽 커서

head와 tail이 언제 바뀌는지, nullptr 참조하는지 주의해서 보면 될 듯

11/18-11/25 PS 3/7