[2021 카카오 인턴십 코딩테스트/c++] 표 편집

✨ 문제풀이

 

양방향 연결 리스트 (Doubly Linked List) 를 이용해서 해결하는 문제이다. 정확성 테스트 뿐만 아니라 효율성 테스트가 있기 때문에 연결 리스트로 해결이 가능하다.

연결 리스트의 작동 원리를 잘 이해하면 구현이 어렵지 않은 문제였다. 그러나 나는 연결 리스트 생각해내는 데 도움을 받아야 했다..😭

 

표가 0 부터 n-1 까지 n개의 행이 있으므로 n개의 노드 배열을 초기화 하고, 각각의 노드에 0 ~ n-1 의 값을 저장한다. 표이기 때문에 처음과 끝은 연결이 되지 않으므로, 맨 처음과 맨 마지막 노드를 제외하고 노드들을 순서대로 양방향으로 연결한다.

 

그리고 나머지는 연결 리스트의 작동 원리를 이용하면 된다.

curr이라는 현재 노드를 가리키는 노드를 만들어서 이동하고, 삭제한다면 연결 리스트에서, 양 옆에 연결된 노드들과 자신의 연결을 끊고 그 두 노드를 연결하면 된다. 이때 삭제하는 노드는 복구될 때 자신의 양 옆 노드들을 기억하고 있어야 하므로 그 데이터는 삭제하지 않는다!!

 

반대로 다시 복구시키는 노드는 자신의 양 옆 노드를 기억하고 있기 때문에, 그 노드들의 연결을 끊고 자신과 연결하면 된다. 이때 중요한건 가장 최근에 삭제한 노드들부터 복구해야 한다는 것이다. 따라서 Last In First Out의 구조를 갖는 Stack에 데이터를 저장하고 하나씩 pop시키면서 데이터를 복구했다.

 

코드를 보는 게 더 이해가 쉬울 수 있는 문제이니 코드를 참조하길 바란다.

 

🗓 코드

#include <bits/stdc++.h>
#include <vector>
#include <stack>

using namespace std;

struct Node
{
    int data;
    Node *prev;
    Node *next;
};

vector<Node *> node(1000001);
Node *curr;

void init(int n)
{
    for (int i = 0; i < n; i++)
    {
        node[i] = new Node();
        node[i]->data = i;
    }

    for (int i = 0; i < n; i++)
    {
        if (i > 0)
            node[i]->prev = node[i - 1];
        if (i < n - 1)
            node[i]->next = node[i + 1];
    }
}

void up(int move)
{
    while (move--)
        curr = curr->prev;
}

void down(int move)
{
    while (move--)
        curr = curr->next;
}

bool isFirstNode(Node *node)
{
    if (!node->prev)
        return true;
    return false;
}

bool isLastNode(Node *node)
{
    if (!node->next)
        return true;
    return false;
}

void remove()
{
    if (!isFirstNode(curr))
        curr->prev->next = curr->next;
    if (!isLastNode(curr))
        curr->next->prev = curr->prev;

    if (!isLastNode(curr))
        curr = curr->next;
    else
        curr = curr->prev;
}

void recover(int v)
{
    if (!isFirstNode(node[v]))
        node[v]->prev->next = node[v];
    if (!isLastNode(node[v]))
        node[v]->next->prev = node[v];
}

int getMove(string s)
{
    return stoi(s.substr(2));
}

string solution(int n, int k, vector<string> cmd)
{
    init(n);

    curr = node[k];
    string answer(n, 'O');
    stack<int> deleted;
    for (string s : cmd)
    {
        if (s[0] == 'U')
        {
            int move = getMove(s);
            up(move);
        }
        else if (s[0] == 'D')
        {
            int move = getMove(s);
            down(move);
        }
        else if (s[0] == 'C')
        {
            deleted.push(curr->data);
            answer[curr->data] = 'X';
            remove();
        }
        else
        {
            int recoveredData = deleted.top();
            deleted.pop();
            answer[recoveredData] = 'O';
            recover(recoveredData);
        }
    }
    return answer;
}