프로그래머스 Level 3 표편집

표편집 (프로그래머스 Level 3)

https://school.programmers.co.kr/learn/courses/30/lessons/81303

스택을 사용하는 것과 ‘연결 리스트’를 사용하는 것은 떠올릴 수 있었으나
세부적인 연결 리스트를 구현하는 중,
실패와 세그먼트 폴트가 발생하여, 복습을 할 겸
다른 블로그를 보게 되었다
(https://eunchanee.tistory.com/677)

양 방향 연결 리스트로, 각 데이터를 관리하여
삭제 및 제거 하되
제거한 녀석은 스택에 넣어
최근의 순서대로 복구할 수 있도록 하는 것이 문제의 핵심이었다
(그걸 알았지만 구현은…)

Code

#include <string>
#include <vector>
#include <stack>

using namespace std;

struct Node 
{
	int val = -1;
	int prev = -1;
	int next = -1;
};

string solution(int n, int k, vector<string> cmd) {
	string answer = "";
	vector<Node> node(n);
	stack<Node> deleted;

	int idx = k;

	for (int i = 0; i < n; i++) 
	{
		answer += "O";

		node[i].val = i;

		if (i > 0) 
		{
			node[i].prev = i - 1;
		}

		if (i < n - 1) 
		{
			node[i].next = i + 1;
		}
	}

	for (int i = 0; i < cmd.size(); i++) 
	{
		string command = cmd[i];

		switch (command[0]) 
		{
		case 'U': 
		{
			int move = stoi(command.substr(2));

			while (move--) 
			{
				idx = node[idx].prev;
			}

			break;
		}

		case 'D': 
		{
			int move = stoi(command.substr(2));

			while (move--) 
			{
				idx = node[idx].next;
			}

			break;
		}

		case 'C': 
		{
			int next = node[idx].next;
			int prev = node[idx].prev;

			deleted.push(node[idx]);

			if (prev > -1) 
			{
				node[prev].next = next;
			}

			if (next > -1) 
			{
				node[next].prev = prev;
			}

			if (next == -1)
			{
				idx = prev;
			}
			else
			{
				idx = next;
			}

			break;
		}

		case 'Z': {
			Node restore = deleted.top();

			int val = restore.val;
			int next = restore.next;
			int prev = restore.prev;

			if (prev > -1) 
			{
				node[prev].next = val;
			}

			if (next > -1) 
			{
				node[next].prev = val;
			}

			deleted.pop();

			break;
		}
		}
	}

	while (deleted.empty() == false)
	{
		int top = deleted.top().val;

		deleted.pop();

		answer[top] = 'X';
	}

	return answer;
}