[연결리스트] (CHECK) 프로그래머스 표 편집 C++

 

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

프로그래머스

 

배열

정확성 30개 통과, 효율성 5개 통과

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

using namespace std;

string solution(int n, int k, vector<string> cmd) {
    string answer = "";
    stack<int> st;
    
    for(int i=0; i<n; i++) answer += "O";
    
    for(auto c : cmd) {
        switch(c[0]) {
            case 'U':
                for(int i=0; i<stoi(c.substr(2)); i++) { // 문자 1개 이상
                    k--;
                    while (answer[k] == 'X') k--; // 연속 확인
                }
                break;
            case 'D':
                for(int i=0; i<stoi(c.substr(2)); i++) {
                    k++;
                    while (answer[k] == 'X') k++;
                }
                break;
            case 'C':
                answer.replace(k, 1, "X");
                st.push(k);
                while (answer[k] == 'X') {
                    if (k == (n-1)) { // k 위, 아래 모두 X
                        while (answer[k] == 'X') k--;
                        break;
                    }
                    k++;
                }
                break;
            case 'Z':
                answer.replace(st.top(), 1, "O");
                st.pop();
                break;
        }
    }
    
    return answer;
}

 

연결리스트

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

using namespace std;

struct Node {
    int idx;
    Node* prev;
    Node* next;
    Node() : idx(-1), prev(NULL), next(NULL) {}
    Node(int idx, Node* prev, Node* next) : idx(idx), prev(prev), next(next) {}
};

Node head, tail;

string solution(int n, int k, vector<string> cmd) {
    string answer(n, 'X');
    stack<Node*> st;
    
    // 초기화
    head.next = &tail;
    tail.prev = &head;
    
    Node* cursor = &head;
    for(int i=0; i<n; i++) {
        Node* temp = new Node(i, cursor, cursor->next);
        cursor->next->prev = temp;
        cursor->next = temp;
        cursor = cursor->next;
    }
    
    // 현재 선택된 행
    cursor = &head;
    for(int i=0; i<k; i++) cursor = cursor->next;
    
    for(auto c : cmd) {
        if (c[0] == 'U') {
            for(int i=0; i<stoi(c.substr(2)); i++) cursor = cursor->prev;
        }
        else if (c[0] == 'D') {
            for(int i=0; i<stoi(c.substr(2)); i++) cursor = cursor->next;
        }
        else if (c[0] == 'C') {
            st.push(cursor->next);
            cursor->next->next->prev = cursor;
            cursor->next = cursor->next->next;
            if (cursor->next->idx == -1) cursor = cursor->prev; // 마지막 행
        }
        else {
            Node* temp = st.top();
            temp->next->prev = temp;
            temp->prev->next = temp;
            if (cursor->next->idx == temp->idx) cursor = cursor->next; // 현재 선택된 행 바뀌지 않게
            st.pop();
        }
    }
    
    // answer
    Node* ptr = &head;
    while (ptr->next->idx != -1) {
        answer.replace(ptr->next->idx, 1, "O");
        ptr = ptr->next;
    }
    
    return answer;
}