프로그래머스 문제 - 표 편집

프로그래머스 표 편집 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

명령어를 기반으로 표의 행을 선택, 삭제, 복구하는 프로그램을 만들어야 합니다.
"U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다.
"D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다.
"C" : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다.
"Z" : 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.
모든 명령어를 수행한 후 표의 상태와 처음 주어진 표의 상태를 비교하여 삭제되지 않은 행은 O, 삭제된 행은 X로 표시하여 문자열 형태로 return해야 합니다.

문제 풀이

행을 선택 후 지우거나 지운 행을 다시 복구하는 작업을 만들어야 합니다.
행의 삭제, 삽입을 빠르게 진행하기 위해 링크드리스트를 사용하는 것이 좋으며, 최근에 삭제가 진행됬던 순서대로 복구를 하기 위해 스택 컨테이너를 사용해줍니다.

링크드리스트를 위해 구조체로 노드를 제작해주고, 앞과 뒤를 알 수 있도록 변수를 넣어줍니다.
노드의 수가 최대 100만개이므로 빠른 노드의 접근을 위해 각 index값의 위치에 노드 주소를 저장해두어 빠르게 접근이 가능하도록 배열로 저장해줍니다.

U와 D는 주어진 값 만큼 노드를 앞으로 이동하거나 뒤로 이동해주면 됩니다.
C가 나와서 노드를 제거해야 할 경우
나중에 복구를 위해 노드 자체를 삭제하지 않고 앞 뒤에 있는 노드들을 연결해주면 됩니다.
맨 앞과 맨 뒤에 있는 노드들을 주의해서 잘 연결해준 후, 지워진 행 다음 행을 선택해주면 됩니다.
만약 맨 뒤에 있는 노드가 삭제될 경우 이전의 행을 선택해주면 됩니다.

Z가 나와서 복구작업을 진행할 경우
스택에 넣어두었던 값들을 꺼내어 꺼낸 값의 노드의 앞과 뒤를 확인하여 연결해주면 됩니다.
복구작업을 하더라도 선택된 행은 바뀌지 않으므로 건드리지 않으면 됩니다.

답은 'O'과 'X'로 이루어진 문자열을 return해야 되기 때문에, 처음에 n만큼 'O'으로 문자열은 만든 후 행이 삭제될 때 삭제된 값의 위치의 문자를 'X'로 바꿔주면 되며, 복구될 경우에는 복구된 값의 위치의 문자를 'O'로 바꿔주면 됩니다.

전체 코드

상당히 난이도가 있는 문제였습니다.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

struct Node{
    int index;
    int prev;
    int next;
    Node(int n, int a, int b) : index(n), prev(a), next(b)  {}
};

string solution(int n, int k, vector<string> cmd) {
    string answer(n, 'O');
    stack<int> cutNodeNum;
    vector<Node> table;
    
    //노드 연결
    for(int i = 0; i < n; i++)
    {
        table.push_back(Node(i, i-1, i+1));
    }
    table[0].prev = -1;
    table[n-1].next = -1;
    
    int curIndex = k;
    for(int i = 0; i < cmd.size(); i++)
    {
        //값만큼 앞의 노드로 이동
        if(cmd[i][0] == 'U')
        {
            int num = stoi(cmd[i].substr(2, cmd[i].size()-2));
            while(num > 0)
            {
                num--;
                curIndex = table[curIndex].prev;
            }
        }
        //값만큼 뒤의 노드로 이동
        else if(cmd[i][0] == 'D')
        {
            int num = stoi(cmd[i].substr(2, cmd[i].size()-2));
            while(num > 0)
            {
                num--;
                curIndex = table[curIndex].next;
            }
        }
        else if(cmd[i][0] == 'C')   //노드 삭제
        {
            //복구작업을 위해 값 저장
            cutNodeNum.push(curIndex);
            Node n = table[curIndex];
            if(n.prev == -1)
            {
                table[n.next].prev = -1;
                curIndex = table[n.next].index;
            }else if(n.next == -1)
            {
                table[n.prev].next = -1;
                curIndex = table[n.prev].index;
            }else
            {
                table[n.prev].next = n.next;
                table[n.next].prev = n.prev;
                curIndex = table[n.next].index;
            }
            answer[n.index] = 'X';
        }else   //삭제를 진행했던 노드를 순서대로 다시 연결
        {
            Node n = table[cutNodeNum.top()];
            if(n.prev == -1)
            {
                table[n.next].prev = n.index;
            }else if(n.next == -1)
            {
                table[n.prev].next = n.index;
            }else
            {
                table[n.prev].next = n.index;
                table[n.next].prev = n.index;
            }
            cutNodeNum.pop();
            answer[n.index] = 'O';
        }
    }
    
    return answer;
}

출저

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