(프로그래머스 C++ KAKAO)표 편집

https://programmers.co.kr/learn/courses/30/lessons/81303?language=cpp 

코딩테스트 연습 - 표 편집

링크드 리스트 형태의 구조체를 선언하여 풀이.

 

Node 구조체를 선언하고 내부에는 val, prev, next를 가지도록 한다.

초기값은 모두 -1을 가지며, for문을 통해 값을 모두 갱신한다.

Node 구조체 배열을 node라는 이름으로 n개의 크기만큼 선언하고,

Node 구조체를 저장할 수 있는 스택("Z" 명령어 처리를 위한 공간)도 선언한다.

 

n 만큼 for문을 실행.

answer에도 "O"를 n개만큼 추가한다.

또한, node[i].val = i로 해주며, prev와 next도 갱신한다.

갱신할 때에는 node의 양 끝이 -1이 되도록 if문 처리를 한다.

 

이후 cmd를 순회하면서 명령어 처리를 한다.

switch 문으로 명령어를 처리.

move는 substr을 이용하여 문자열을 자르고, int형으로 바꾼다.

 

"U", "D" 명령어는 move 만큼 k를 이동시킨다.

이동은 node[k].next나 node[k].prev로 갱신시키면 된다.

 

"C" 명령어.

노드를 지우기 위해 deleted 스택에 node[k]를 push하고,

node[k]의 next와 prev도 별도의 변수에 저장한다.

만약 prev가 -1이라면 현재 k 번째 노드는 가장 처음에 위치하기 때문에 이전 노드를 next로 이어주지 않아도 된다.

만약 next가 -1이라면 현재 k 번째 노드는 가장 끝에 위치하기 때문에 다음 노드를 prev로 이어주지 않아도 된다.

 

이 두 조건이 핵심이며, 연결이 끝나면 k도 이동시킨다.

k를 이동시킬 때에도 next가 -1이 아닌 경우 next로 저장하고, 그렇지 않다면 prev로 저장한다.

 

"Z" 명령어.

스택에 담겨있는 노드를 꺼내서 복구 시킨다.

val, next, prev를 스택의 top에 있는 값으로 저장.

 

만약 prev가 -1이 아니라면 prev의 다음 노드를 val로 연결.

만약 next가 -1이 아니라면 next의 이전 노드를 val로 연결.

마지막은 pop()을 하여 스택을 위에서 비워주도록 한다.

 

명령어 처리가 끝나면 deleted에 남아있는 val을 이용해 "X"로 바꿔주면 된다.

#include <string>
#include <vector>
#include <iostream>
#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 = "";
    struct Node node[n];
    stack<Node> deleted;
    
    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--){
                    k = node[k].prev;
                }
                
                break;
            }
                
            case 'D':{
                int move = stoi(command.substr(2));
                
                while(move--){
                    k = node[k].next;
                }
                
                break;
            }
                
            case 'C':{
                int next = node[k].next;
                int prev = node[k].prev;
                
                deleted.push(node[k]);
                
                if(prev > -1){
                    node[prev].next = next;
                }
                
                if(next > -1){
                    node[next].prev = prev;
                }
                
                k = next > -1 ? next : prev;
                
                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()){
        int top = deleted.top().val;
        
        deleted.pop();
        
        answer[top] = 'X';
    }
    
    return answer;
}