프로그래머스 표 편집 혼내주기

 

 

 

2021 카카오톡 채용연계형 인턴쉽 코딩테스트 3번 문제.
doubly linked list 클래스를 구현하고 스택을 이용해 복구하는 부분을 넣어줘서 풀었다.

그땐 세그먼트 트리를 몰라서 이렇게 풀었는데, 지금 다시 풀게 된다면 k번째 수 세그로 풀 것 같다.

 

 

 

#include <vector>
#include <string>
#include <stack>
#include <list>
#include <iostream>
using namespace std;

struct node {
    int idx;
    node* prev;
    node* next;
    node(int i) {
        idx = i;
        next = NULL;
        prev = NULL;
    }
};

struct doublyLinkedList {
    node* head;
    node* tail;
    stack<node*> history;
    doublyLinkedList() {
        head = new node(-1);
        tail = new node(-1);
        head->next = tail;
        tail->prev = head;
    }
    void push_back(int idx) {
        node* newNode = new node(idx);
        newNode->prev = tail->prev;
        newNode->next = tail;
        tail->prev->next = newNode;
        tail->prev = newNode;
    }

    node* erase(node* curr) {
        history.push(curr);
        curr->prev->next = curr->next;
        curr->next->prev = curr->prev;
        return curr->next;
    }

    void recover() {
        node* curr = history.top();
        curr->prev->next = curr;
        curr->next->prev = curr;
        history.pop();
    }
};

string solution(int n, int k, vector<string> cmd) {
    string answer = "";

    doublyLinkedList dll = doublyLinkedList();
    for(int i = 0; i < n; ++i) {
        dll.push_back(i);
    }

    node* it = dll.head->next;
    for(int i = 0; i < k; ++i) {
        it = it->next;
    }
    
    for(string c : cmd) {
        if(c[0] == 'U') {
            int num = 0;
            for(int i = 2; i < c.size(); ++i) {
                num *= 10;
                num += c[i]-'0';
            }
            for(int i = 0; i < num; ++i) {
                it = it->prev;
            }
        }
        else if(c[0] == 'D') {
            int num = 0;
            for(int i = 2; i < c.size(); ++i) {
                num *= 10;
                num += c[i]-'0';
            }
            for(int i = 0; i < num; ++i) {
                it = it->next;
            }
        }
        else if(c[0] == 'C') {
            it = dll.erase(it);
            if(it == dll.tail)
                it = dll.tail->prev;
        }
        else {
            dll.recover();
        }
    }

    node* itt = dll.head->next;
    for(int i = 0; i < n; ++i) {
        if(i == itt->idx) {
            answer += 'O';
            itt = itt->next;
        }
        else {
            answer += 'X';
        }
    }

    return answer;
}

int main() {
    vector<string> cmd = {
        "D 2","C","U 3","C","D 4","C","U 2","Z","Z"
    };

    cout << solution(8, 2, cmd);
}