[c++][프로그래머스] 표 편집

프로그래머스 표 편집 [2021 카카오 채용연계형 인턴십]
https://programmers.co.kr/learn/courses/30/lessons/81303

코딩테스트 연습 - 표 편집

문제 풀이

• 이 문제는 이중 연결 리스트(Doubly linked list)를 사용하여 풀었습니다.
• U, D 커맨드는 X만큼 prev or next로 이동합니다.
• C 커맨드는 현재 노드를 스택에 담고 cur->prev와 cur->next를 서로 연결시켜줍니다.
• Z 커맨드는 스택에서 노드 하나를 꺼내면 해당 노드에는 이전에 연결되어 있던 노드들의 정보가 남아있기 때문에 그에 따라 다시 원래 자리로 연결시켜줍니다. 
  • top이라는 노드를 꺼냈다면, top->prev->next = top 이런 식으로 꺼낸 노드를 넣어주면 됩니다.
  • 마찬가지로 top->next->prev = top 도 해줍니다. 
• C, Z 커맨드에서 노드끼리 연결할 때 prev or next가 nullptr인지 잘 확인하여 연결시켜줍니다. 
• 표에 남아있는 행들을 O 표시 해주기 위해 먼저 제일 앞 노드로 이동한 후, 다시 맨 뒤까지 이동하면서 자신의 index를 O로 바꿔줍니다.

코드

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

using namespace std;

struct Node {
    int idx;
    
    Node* prev;
    Node* next;
    
    Node(int _idx) : idx(_idx), prev(nullptr), next(nullptr) {}
};

string solution(int n, int k, vector<string> cmds) {
    string answer(n, 'X');
    vector<Node*> v;
    stack<Node*> st;
    
    for(int i=0; i<n; ++i) v.push_back(new Node(i));
    
    v[0]->next = v[1];
    v[n-1]->prev = v[n-2];
    
    for(int i=1; i<n-1; ++i) {
        v[i]->prev = v[i-1];
        v[i]->next = v[i+1];
    }
    
    Node* cur = v[k];
    
    for(string cmd: cmds) {
        if(cmd[0] == 'U') {
            int move = stoi(cmd.substr(2));
            
            while(move--) cur = cur->prev;
        }
        else if(cmd[0] == 'D') {
            int move = stoi(cmd.substr(2));
            
            while(move--) cur = cur->next;
        }
        else if(cmd[0] == 'C') {
            st.push(cur);
            
            if(cur->prev == nullptr) {
                cur->next->prev = nullptr;
                cur = cur->next;
            }
            else if(cur->next == nullptr) {
                cur->prev->next = nullptr;
                cur = cur->prev;
            }
            else {
                cur->prev->next = cur->next;
                cur->next->prev = cur->prev;
                cur = cur->next;
            }
        }
        else {
            Node* top = st.top(); st.pop();
            
            if(top->prev != nullptr) top->prev->next = top;
            if(top->next != nullptr) top->next->prev = top;
        }
    }
    
    while(cur->prev != nullptr) cur = cur->prev; // 제일 앞으로 이동
    while(cur != nullptr) { // 제일 뒤로 이동하면서 자신의 index 'O'로 바꿈
        answer[cur->idx] = 'O';
        cur = cur->next;
    } 

    return answer;
}

실행 결과