표 편집 [Lv. 3] (C++)

프로그래머스

표를 편집하는 문제입니다.

선택 행을 위, 아래로 옮기고 행 삭제, 되돌리기 기능을 구현하면 됩니다.

 

풀이 방법

이 문제의 핵심은 아래와 같습니다.

cmd에 등장하는 모든 X들의 값을 합친 결과가 1,000,000 이하인 경우만 입력으로 주어집니다.

선택 행을 이동하는 수가 100만 이하, 즉 탐색 속도가 정말 느린 이중 연결 리스트를 이용할 수 있다는 이야기입니다.

---

이중 연결 리스트를 이용할 수 있다면 문제를 정말 쉽게 풀 수 있을 것입니다.

행 이동은 N의 속도로 해결,

삭제의 경우 왼쪽 노드의 오른쪽 = 나의 오른쪽,  오른쪽 노드의 왼쪽 = 나의 왼쪽

되돌리기는 삭제한 노드를 stack에 저장해두고 하나씩 뺸 후

왼쪽 노드의 오른쪽 = 나, 오른쪽 노드의 왼쪽 = 나로 수정하면 됩니다.

---

하지만 문제가 하나 더 남아있습니다.

삭제한 노드인지 체크하는 부분입니다.

 

우선 n크기 만큼 'O'를 채워줍니다.

n == 8
"OOOOOOOO"

 

노드에 index 정보를 넣어두고

마지막에 남은 삭제 리스트를 순회하여

삭제된 노드의 index를 참고해 answer를 수정해주면 됩니다.

 

정답 코드

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

using namespace std;
class Node
{
    public:
    
    int n;
    Node* prev;
    Node* next;
    
    public:
        Node(int value, Node* p, Node* n) : n(value), prev(p), next(n){}
};

string solution(int n, int k, vector<string> cmd) {
    
    Node* root = new Node(0, nullptr, nullptr);
    Node* curNode = root;
    
    for(int i = 1; i < n; i++)
    {
        root->next = new Node(i, root, nullptr);;
        root = root->next;
    }
    
    for (int i = 0; i < k; i++)
        curNode = curNode->next;
        
    stack<Node*> removes;
    for (auto& c : cmd)
    {
        if (c == "C")
        {
           removes.push(curNode);

            
            if (curNode->prev != nullptr)
                curNode->prev->next = curNode->next;
            
            if (curNode->next != nullptr)
                curNode->next->prev = curNode->prev;
            
            if (curNode->next == nullptr)
                curNode = curNode->prev;
            else
                curNode = curNode->next;
   
        }
        else if (c == "Z")
        {
            Node* node = removes.top(); removes.pop();
            if (node->prev != nullptr)
                node->prev->next = node;
            
            if (node->next != nullptr)
                node->next->prev = node;
        }
        
        else
        {
            int cnt = stoi(c.substr(2));
            
            for (int i = 0; i < cnt; i++)
            {
                if (c[0] == 'U')
                    curNode = curNode->prev;
                else
                    curNode = curNode->next;
            }
            
        }
    }
    
    string answer(n, 'O');
    while(!removes.empty())
    {
        answer[removes.top()->n] = 'X';
        removes.pop();
    }
    

    return answer;
}