[프로그래머스 lv3] 표 편집 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해당 문제는 2021 카카오 채용연계형 인턴십 문제로 공식 해설이 있습니다.

2021 카카오 인턴십 for Tech developers 코딩 테스트 해설

 

해설

표를 구성하고, 이동(U, D), 삭제(C), 복구(Z) 명령어를 구현하는 문제이다.

이 문제의 핵심은 표를 구성할 자료구조를 선택하는 것이다.

 

가장 먼저 생각했던 자료구조는 set이었다.

U X, D X 명령어에서 X의 총합이 1000000 이하이고, set에서는 원소의 삭제가 log(n)에 가능하므로 총 시간복잡도는 최대 t = 1000000 + cmd.size()*log(n) 이 된다. 

cmd와 n의 최대 범위를 고려했을 때 1초 내에 연산 가능하므로 통과할 것이라 생각했는데 이런! 효율성 통과가 안된다.

여러 블로그글들을 살펴보니 예전에는 set 풀이가 통과되었는데 어느 날 채점 방식(?)이 수정된 것 같다고 한다.

 

시간복잡도를 더 줄일 수 있는 방법으로 연결리스트를 활용하는 방법이 있다.

c++에 list STL이 있긴 하지만, 안타깝게도 삭제를 우리가 원하는 대로 처리해 주어야 하기 때문에 STL을 사용할 수 없다. 대신, 직접 양방향 노드를 만들어 구현해주어야 한다.

 

struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int data, Node* prev, Node* next) : data(data), prev(prev), next(next) {}
};

 

prev 포인터와 next 포인터를 가지는 노드를 만들고, 이를 연결하여 0부터 n-1까지의 수가 저장된 연결리스트를 만든다. 이후, Node* cur 포인터가 k번째 노드를 가리키도록 세팅한다. 명령어들은 다음과 같이 구현한다.

 

1) U X 명령어의 경우, X 만큼 cur 포인터를 prev 방향으로 이동시킨다.

2) D X 명령어의 경우, X 만큼 cur 포인터를 next 방향으로 이동시킨다.

3) C 명령어의 경우, cur 포인터에 대한 정보를 스택에 넣고, cur의 이전노드와 다음 노드를 연결시킨다. 이렇게 하면 기존의 노드 정보는 삭제하지 않고 연결 정보만 수정하면 되기 때문에 O(1)에 처리 가능하다. 

 

 

출처: KKAO TECH BLOG

 

 

4) Z 명령어의 경우, 스택의 가장 윗쪽에 있는 노드 정보를 받아와 이를 다시 연결시킨다. 다시 연결할 노드 포인터를 tmp 라 할 때, tmp의 왼쪽 노드가 다시 tmp를 가리키고, tmp의 오른쪽 노드가 다시 tmp를 가리키도록 한다. 이 역시 O(1)에 처리 가능하다.

 

모든 명령어를 처리해준 뒤, 삭제된 노드들은 스택에 들어있으므로 스택에 들어있는 번호에 대하여 문자를 X로 수정해준다.

결과 문자열을 리턴하면 정답이다.

 

 

스택 풀이(효율성 미통과)

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int x;
char c;
stack<int> st;
set<int> sset;
set<int>::iterator it;

void cmdU() {
    it = prev(it, x);
}

void cmdD() {
    it = next(it, x);
}

void cmdC() {
    st.push(*it);
    it = sset.erase(it);
    if (it == sset.end()) it = prev(it);
}

void cmdZ() {
    sset.insert(st.top());
    st.pop();
}

string solution(int n, int k, vector<string> cmd) {
    
    for (int i=0; i<n; i++) sset.insert(i);
    
    it = sset.begin();
    it = next(it, k);
      
    for (auto s : cmd) {
        sscanf(s.c_str(), "%c %d", &c, &x);
        if (c == 'U') cmdU();
        else if (c == 'D') cmdD();
        else if (c == 'C') cmdC();
        else if (c == 'Z') cmdZ();
    }
    
    string ans = string(n, 'X');
    for (auto c : sset) ans[c] = 'O';
    return ans;
}

 

 

연결리스트풀이(효율성 통과)

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int data, Node* prev, Node* next) : data(data), prev(prev), next(next) {}
};

void cmdU(Node** pcur, int x) {
    for (int i=0; i<x; i++) *pcur = (*pcur)->prev;
}

void cmdD(Node** pcur, int x) {
    for (int i=0; i<x; i++) *pcur = (*pcur)->next;
}

void cmdC(Node** pcur, stack<Node*>& st) {
    
    st.push(*pcur);
    if ((*pcur)->prev != NULL)
        (*pcur)->prev->next = (*pcur)->next;
    if ((*pcur)->next != NULL)
        (*pcur)->next->prev = (*pcur)->prev;
    if ((*pcur)->next == NULL) (*pcur) = (*pcur)->prev;
    else (*pcur) = (*pcur)->next;
}

void cmdZ(stack<Node*>& st) {
    
    Node* tmp = st.top();
    st.pop();
    if (tmp->prev != NULL)
        tmp->prev->next = tmp;
    if (tmp->next != NULL)
        tmp->next->prev = tmp;
}

string solution(int n, int k, vector<string> cmd) {
    
    Node* node = new Node(0, NULL, NULL);
    Node* cur = node;
    stack<Node*> st;
    
    for (int i=1; i<n; i++) {
        node->next = new Node(i, node, NULL);
        node = node->next;
    }
    
    for (int i=0; i<k; i++) cur = cur->next;
    
    for (auto s : cmd) {
        char c;
        int x;
        sscanf(s.c_str(), "%c %d", &c, &x);
        if (c == 'U') cmdU(&cur, x);
        else if (c == 'D') cmdD(&cur, x);
        else if (c == 'C') cmdC(&cur, st);
        else if (c == 'Z') cmdZ(st); 
    }
    
    string ans = string(n, 'O');
    while (!st.empty()) {
        ans[st.top()->data] = 'X';
        st.pop();
    }
    return ans;
}