[1일 1알고] 표 편집

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

프로그래머스

 

이런 문제는 간단하게 가라로 풀려고 하면 꼭 수렁에 빠지게 되네요

 

보면 기본적으로 제거한 행(노드)을 저장하기 위한 Stack이 필요할 것입니다.

(Z의 규칙이 마지막에 삭제된 노드 복구이기 때문에)

 

그리고 삭제한 노드를 복구하기 위해서는 단순히 삭제되었다고 bool등으로 체크만 한 뒤 탐색 시 이를 지나치는 방법과

아예 연결 리스트로 만들어 구현하는 방법이 있습니다.

 

저는 제시된 예시의 계산 횟수가 커보여서 연결리스트를 만들었습니다.

---

struct Node
{
    Node* prev = nullptr;
    Node* next = nullptr;
    bool check;
    int num;
};

//cmd의 각 원소는 "U X", "D X", "C", "Z" 중 하나입니다.
string solution(int n, int k, vector<string> cmd) {
    string answer = "";

    vector<Node*> nodes(n);
    Node* prev = nullptr;
    Node* next = nullptr;

    Node* newNode = new Node();
    newNode->prev = prev;
    newNode->num = 0;
    nodes[0] = newNode;

    prev = newNode;

    for (int i = 1; i < n; ++i)
    {
        Node* newNode = new Node();
        newNode->prev = prev;
        newNode->prev->next = newNode;
        newNode->num = i;
        nodes[i] = newNode;

        prev = newNode;
    }

    Node* cur = nodes[k];
    stack<Node*> removed;

    for (int i = 0; i < cmd.size(); ++i)
    {
        if (cmd[i][0] == 'U')
        {
            int x = stoi(cmd[i].substr(2));
            for (int j = 0; j < x; ++j)
            {
                cur = cur->prev;
            }
        }
        else if (cmd[i][0] == 'D')
        {
            int x = stoi(cmd[i].substr(2));
            for (int j = 0; j < x; ++j)
            {
                cur = cur->next;
            }
        }
        else if (cmd[i][0] == 'C')
        {
            removed.push(cur);

            if (cur->prev != nullptr)
                cur->prev->next = cur->next;

            if (cur->next != nullptr)
                cur->next->prev = cur->prev;

            if (cur->next == nullptr)
            {
                cur = cur->prev;
            }
            else
            {
                cur = cur->next;
            }
        }
        else if (cmd[i][0] == 'Z')
        {
            Node* removedNode = removed.top();
            removed.pop();
            if (removedNode->prev != nullptr)
                removedNode->prev->next = removedNode;

            if (removedNode->next != nullptr)
                removedNode->next->prev = removedNode;
        }
    }
    
    vector<bool> checks(n, true);

    while (!removed.empty())
    {
        Node* removedNode = removed.top();
        removed.pop();
        checks[removedNode->num] = false;
    }

    for (int i = 0; i < n; ++i)
    {
        if (checks[i])
            answer += 'O';
        else
            answer += 'X';
    }
    return answer;
}

필요없는 데이터나 연산도 코딩하다보니 생겼지만 정리하지는 않았습니다.