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

Pixabay로부터 입수된 Hands off my tags! Michael Gaida님의 이미지 입니다.

---

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

프로그래머스

 이 문제는 표의 행 개수, 처음 위치, 명령어들이 주어졌을 때, 모든 명령어를 실행한 후의 결과를 반환하는 문제이다. 처음에는 이 문제를 단순하게 bool타입의 배열을 이용해서 문제를 풀었더니 시간 초과가 떴었다. 어찌 보면 당연한데, 최악의 경우를 가정한 경우의 행의 개수는 1,000,000개이고 명령어는 200,000개이다. 모든 명령어마다 행의 처음부터 끝까지 이동해야 할 경우, 이동만 1,000,000 x 200,000 = 200,000,000,000번 해야 한다. 그렇기에 단순히 배열 탐색으로 문제를 푼다면 시간 초과가 나와도 이상할 것이 없다.

 

이중 연결 리스트

 그렇기에 다른 방법을 모색해야 한다. 그리고 이에 대한 해결책으로 연결 리스트(Linked List)가 있다. 연결 리스트란 이름 그대로 각 노드들이 앞뒤로 이어져있는 리스트를 이야기한다. 그 중에서도 앞뒤로 모두 이어진 이중 연결 리스트를 이용할 것이다. 왜냐하면 주어진 명령어에는 위아래(앞뒤) 이동이 모두 포함되어 있기 때문이다. 하지만 이걸로는 부족하다. 만약 특정 노드가 제거되었을 경우, 이를 연결 리스트에서 완전히 제거해야 한다. 제거된 노드들을 따로 저장해두기 위해 스택을 이용할 것이다. 스택이란 간단히 말해서 프링글스 통과 같이 가장 처음 넣은 게 가장 처음 나오는 구조이다. 그리고 문제의 조건에서 삭제한 노드를 복구할 경우, 가장 최근에 삭제된 노드를 복구하라고 하였기에 스택이 가장 적합하다 할 수 있다.

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

using namespace std;

typedef struct NODE {
    NODE* prev;
    NODE* next;
    int data;
    
    NODE(int _data): data(_data) {
        prev = NULL;
        next = NULL;
    }
} Node;

typedef struct LINKEDLIST {
    Node* head;
    Node* tail;
    
    LINKEDLIST(): head(NULL), tail(NULL) {}
    
    void Insert(int n);
    Node* Remove(Node* node);
    void Restore(Node* node);
} LinkedList;

void LinkedList::Insert(int n) {
    Node* newNode = new Node(n);
    
    if (this->head == NULL) {
        this->head = newNode;
        this->tail = newNode;
    } else {
        this->tail->next = newNode;
        newNode->prev = this->tail;
        this->tail = newNode;
    }
}

Node* LinkedList::Remove(Node* node) {
    if (this->head == node) {
        node->next->prev = NULL;
        this->head = node->next;
        
        return node->next;
    } else if (this->tail == node) {
        node->prev->next = NULL;
        this->tail = node->prev;
        
        return node->prev;
    } else {
        node->prev->next = node->next;
        node->next->prev = node->prev;
        
        return node->next;
    }
}

void LinkedList::Restore(Node* node) {
    if (node->prev == NULL) {
        this->head->prev = node;
        this->head = node;
    } else if (node->next == NULL) {
        this->tail->next = node;
        this->tail = node;
    } else {
        node->next->prev = node;
        node->prev->next = node;
    }
}

LinkedList* list;
stack<Node*> stk;

void MakeLinkedList(int n)
{
    list = new LinkedList();
    
    for (int i = 0; i < n; ++i)
        list->Insert(i);
}

string solution(int n, int k, vector<string> cmd) {
    string answer = "";
    
    MakeLinkedList(n);
    
    Node* iter = list->head;
    
    for (int i = 0; i < k; ++i)
        iter = iter->next;
    
    for (int i = 0; i < cmd.size(); ++i)
    {
        string curCmd = cmd[i];
            
        char cmdType = curCmd[0];
        
        switch (curCmd[0])
        {
        case 'U':
        {
            int movingTurn = stoi(curCmd.substr(2));

            for (int m = 0; m < movingTurn; ++m)
                iter = iter->prev;

            break;
        }
        case 'D':
        {
            int movingTurn = stoi(curCmd.substr(2));

            for (int m = 0; m < movingTurn; ++m)
                iter = iter->next;

            break;
        }
        case 'C':
        {
            stk.push(iter);
            iter = list->Remove(iter);

            break;
        }
        case 'Z':
        {
            Node* restored = stk.top();
            stk.pop();

            list->Restore(restored);

            break;
        }
        }
    }
    
    for (int i = 0; i < n; ++i)
        answer += "O";
    
    while(!stk.empty())
    {
        Node* restored = stk.top();
        stk.pop();
        
        answer[restored->data] = 'X';
    }
    
    
    return answer;
}

 

 

---

연결 리스트

https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8

연결 리스트 - 위키백과, 우리 모두의 백과사전

스택

https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D

스택 - 위키백과, 우리 모두의 백과사전