[Programmers] 표 편집(Lv.3)

풀이 소요시간 : 60분 초과(실패)

연결 리스트 를 구현할 줄 모르면 풀 수 없는 문제였다. 필자는 일반적인 구현으로 시간초과가 발생하여 효율성 테스트를 통과하지 못했다.

삽입 과 삭제 가 빈번히 발생하는 유형의 문제는 연결 리스트를 구현하여 풀이할 수 있다.
이번 기회에 구현 방식을 숙달하는 것을 목표로 삼자.

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

위의 Node 라는 구조체를 선언하여 연결 리스트의 노드 를 구현한다.

	for(int i = 0; i < n; i++)
    {
        node[i].val = i;
        if(i > 0) node[i].prev = i - 1;
        if(i < n - 1) node[i].next = i + 1;
    }

이후 각 노드를 연결시키는 방식은 다음과 같다. 첫 번째 노드와 마지막 노드를 주의하자.

노드의 삭제는 다음과 같다.

case 'C' : {
                Delete.push(node[k]);
                int prev = node[k].Prev;
                int next = node[k].Next;
                
                //마지막 노드가 아니라면
                if(node[k].Next != -1)
                {
                    node[next].Prev = prev;
                }
                
                //첫번째 노드가 아니라면
                if(node[k].Prev != -1)
                {
                    node[prev].Next = next;
                }
                
                break;
            }

마찬가지로 첫 번째 노드와 마지막 노드를 주의한다.

위의 코드에서 삭제된 노드는 node[k] 이다. **node[k].next = -1** 인 경우 마지막 노드임을 뜻한다. 마지막 노드가 삭제된 경우 그 전 prev 노드가 마지막 노드가 된다. 즉, node[prev].next = -1(next) 이 되어야한다.

node[k].prev = -1 인 경우 첫 번째 노드임을 뜻한다. 첫 번째 노드가 삭제된 경우 그 다음 노드가 첫 번째 노드가 된다. 따라서 node[next].prev = -1(prev) 이 되어야한다.

전체 코드

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

using namespace std;

//삽입과 삭제가 빈번한 유형 : 연결리스트의 직접 구현
//연결리스트 
struct Node{
    int Prev = -1;
    int Val = -1;
    int Next = -1;
};


stack<Node> Delete;

string solution(int n, int k, vector<string> cmd) {
    Node node[n];
    string Ans = "";
    for(int i = 0; i < n; i++)
    {
        Ans += "O";
        node[i].Val = i;
        if(i > 0) node[i].Prev = i - 1;
        if(i < n - 1) node[i].Next = i + 1;
    }
    //연결리스트 초기화
    
    for(auto str : cmd)
    {
        int C = str[0]; 
        switch(C) {
            case 'U' : {
                int move = stoi(str.substr(2));
                while(move--)
                {
                    k = node[k].Prev;
                }
                break;
            }
            case 'D' : {
                int move = stoi(str.substr(2));
                while(move--)
                {
                    k = node[k].Next;
                }
                break;
            }
            case 'C' : {
                Delete.push(node[k]);
                int prev = node[k].Prev;
                int next = node[k].Next;
                
                //마지막 노드가 아니라면
                if(node[k].Next != -1)
                {
                    node[next].Prev = prev;
                }
                
                //첫번째 노드가 아니라면
                if(node[k].Prev != -1)
                {
                    node[prev].Next = next;
                }
                
                k = (next == -1) ? prev : next;
                
                break;
            }
            case 'Z' : {
                Node restore = Delete.top();
                Delete.pop();
                
                int val = restore.Val;
                int prev = restore.Prev;
                int next = restore.Next;
                
                //복구 노드가 첫 노드가 아니라면
                if(prev != -1) node[prev].Next = val;
                
                //복구 노드가 마지막 노드가 아니라면
                if(next != -1) node[next].Prev = val;
                
                break; 
            }
        }
    }
    
    
    //출력
    while(!Delete.empty())
    {
        Node node = Delete.top();
        Delete.pop();
        
        int Index = node.Val;
        Ans[Index] = 'X';
    }
    
    
    return Ans;
}