[2021 카카오 채용 연계 인턴십] 표 편집 (c++)

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

프로그래머스

위의 문제에 대한 해설입니다.

우선 문제의 효율성 테스트를 통과하려면 꽤 큰 input에도 대처가 가능해야하는데, 이 때문에 문제 그대로 단순히

삽입, 삭제를 그때 그때 수행하는 것 만으론 시간복잡도가 오버된다.

따라서 삽입, 삭제를 실제로 행하지 않거나, 혹은 실제로 삽입, 삭제를 진행하되, 그 효율을 좋게 만들어야만 해결할 수 있다.

 

내 경우는 linked list 자료구조를 통해 해결했다. linked list 자료구조의 경우, sequential한 탐색이 아니라면 

적합하지 못한 자료구조이고, vector, queue,stack과 같이 c++ 헤더를 통해 가져올 수 없다.

다만 삽입, 삭제의 경우, 삽입, 삭제 위치를 구할 필요가 없다면, O(1)으로 해결 가능하다. 

 

이 문제는 '현재 위치' 에서의 삽입, 삭제에 관한 문제이므로 linked list가 적합하다고 볼 수 있다.

추가로 'Z' 명령어를 구현하여 최근 삭제된 노드를 복구할 수 있어야하는데, 이는 stack 자료구조를 사용하여 지운 노드를 저장하는 것으로 최근 삭제된 순서대로 복구가 가능하도록 구현하였다.

여기서 linked list 자료구조의 강점을 또 다시 활용하는데, 삭제된 링크드 리스트는, 삭제되기전에 보유하고 있던

previous_node의 정보와 next_node의 정보를 그대로 가지고 있기에, 만약 'Z' 명령어로 복구해야될 경우, 복구할 위치를 찾아서 삽입할 필요 없이, 기존에 보유한 이전 노드, 다음 노드 정보를 기반으로 O(1)의 시간 복잡도로 복구가 가능하다.  

 

 

 

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


struct Node { // 양방향 연결 리스트
    int n;
    Node* prev;
    Node* next;
    Node(int n, Node* prev, Node* next) : n(n), prev(prev), next(next) {}   //생성자
};


stack<Node*>  stk; //삭제된 노드를 저장하는 stack 자료구조
string solution(int n, int k, vector<string> cmd) {
    //string answer = "";
    string answer(n, 'X');
    Node* it = new Node(0, NULL, NULL); //각 개체는 생성 후 개별적인 객체로 유지됨. 포인터로 가르켜야한다 .


    Node* cur; //현재 위치를 가르키는 포인터.

    for (int i = 1; i < n; i++) {
        it->next = new Node(i, it, NULL);
        it = it->next;
        if (i == k)
            cur = it;
    }



    for (auto c : cmd) {
        if (c[0] == 'U') {
        
            int num = stoi(c.substr(2, 8));   
            while (num--) cur = cur->prev;
        }
        else if (c[0] == 'D') {
            int num = stoi(c.substr(2, 8));
            while (num--)cur = cur->next;
        }
        else if (c[0] == 'C') {
            stk.push(cur);
            if (cur->prev != NULL) cur->prev->next = cur->next;
            if (cur->next != NULL) cur->next->prev = cur->prev;
            if (cur->next == NULL) cur = cur->prev;
            else cur = cur->next;


        }
        else if (c[0] == 'Z') {
            if (!stk.empty()) {
                Node* tmp = stk.top();
                if (tmp->prev != NULL) tmp->prev->next = tmp;
                if (tmp->next != NULL) tmp->next->prev = tmp;
                stk.pop();
            }

        }
    }
    while (cur->prev != NULL)cur = cur->prev; //첫번째 연결 리스트로 위치 이동.
    while (cur != NULL) { //시작~ 끝 완전탐색.
        answer[cur->n] = 'O'; //삭제되지 않은 노드들을 표시한다.
        cur = cur->next;
    }
    return answer;
}