프로그래머스 - 표 편집

프로그래머스 - 표 편집

풀이 방식은 세그먼트 트리와 이중 연결리스트로 두 가지이다.
Set, Stack을 이용한 풀이도 있는 것 같은데, 아마도 세그먼트 트리나 이중 연결리스트로 하는 것이 더 빠를 것 같아서 따로 코드를 짜지는 않았다.

U, D가 들어올 때마다 링크드리스트를 순회하는 것처럼 X만큼 순회하면 된다.
먼저 이중 연결리스트의 경우 삭제될 때마다 리스트에서 지워준다.
평범하게 링크드리스트에서 삭제할때처럼 해주면 된다.
추가적으로 삭제한 뒤 현재 노드의 다음 노드로 현재 노드를 업데이트 해줘야한다.
만약 현재 노드가 마지막 노드(현재 노드의 다음 노드가 없는 경우)일 경우에는 현재 노드를 현재 노드의 이전 노드로 업데이트해주면 된다.

또한 추후에 복구하기 위해서 삭제할 때마다 현재 노드의 인덱스를 Stack에 Push 해준다.
복구할 때에는 Stack의 top을 보고, 해당 인덱스를 가진 Node를 복구해주면 된다.
이 때, 복구하려는 앞 뒤 노드가 모두 삭제되어 있는 경우는 없기 때문에 리스트에 Insert하듯 복구해주면 된다.

링크드리스트 코드는 아래와 같다.

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

using namespace std;

typedef struct __node {
    int idx;
    struct __node *prev;
    struct __node *next;
}node;

int get_num(string str)
{
    string s;
    for(int j=2;j<str.size();j++) 
        s.push_back(str[j]);
    return stoi(s);
}

string solution(int n, int k, vector<string> cmd) {
    string answer = "";
    int pos = k;
    node *arr[n];
    int alive[n]; 
    
    for(int i=0;i<n;i++) {
        arr[i] = new node;
        arr[i]->idx = i;
        alive[i] = 1;
    }
    for(int i=0;i<n;i++) {
        if(i == 0)
            arr[i]->prev = NULL;
        else
            arr[i]->prev = arr[i-1];
        if(i == n - 1)
            arr[i]->next = NULL;
        else
            arr[i]->next = arr[i+1];
    }
    
    
    node *current_node = arr[k];
    
    stack<int> st;
    for(int i=0;i<cmd.size();i++) {
        char command = cmd[i][0];
        //printf("Current : %d\n", current_node->idx);    
        if(command == 'Z' || command == 'C') {
            if(command == 'C') {
                st.push(current_node->idx);
                alive[current_node->idx] = 0;
                if(current_node->prev) current_node->prev->next = current_node->next;
                if(current_node->next) current_node->next->prev = current_node->prev;
                
                if(current_node->next) current_node = current_node->next;
                else current_node = current_node->prev; 
            } else {
                int restored_pos = st.top(); st.pop();
                alive[restored_pos] = 1;
                
                node *restored = arr[restored_pos];
                if(restored->prev)
                    restored->prev->next = restored;
                if(restored->next)
                    restored->next->prev = restored;
            }
        } else {
            int num = get_num(cmd[i]);
            if(command == 'U') {
                while(1) {
                    if(!num)
                        break;
                    current_node = current_node->prev;
                    num--;
                }
            } else {
                 while(1) {
                    if(!num)
                        break;
                    current_node = current_node->next;
                    num--;
                }
            }
        }
    }
    
    for(int i=0;i<n;i++) {
        if(alive[i])
            answer.push_back('O');
        else
            answer.push_back('X');
    }
    
    return answer;
}

다음은 세그먼트 트리 코드이다.
본 문제에서 세그먼트 트리는 해당 구간에서 현재 삭제되지 않은 노드들의 갯수를 의미한다.
C연산을 할 때마다 Segment Tree 상의 Index를 지워주면 되고, 스택에 지워진 Segment Tree Node가 원래 배열에서 몇 번째 Index를 Push해주면 된다. (백준 요세푸스 문제랑 비슷하다)

다음으로 복구를 할 때에는 실제 배열 인덱스 이용해서 Segment Tree Node들을 업데이트해주면 된다. (Leaf부터 Root로 올라가면서 해당 Node들의 값을 1씩 증가시키면 된다)
이를 위해 Segment Tree Init 과정에서 실제 배열 인덱스들이 Segment Tree에서 몇 번째 Node에 위치하는지를 기록해두었다.

약간 까다로운 부분은 복구될 때 가장 최근 삭제된 노드의 실제 인덱스를 기준으로 현재 가리키고 있는 Segment Tree 상의 Index를 증가시켜줄지 말지를 결정해야 한다는 점이다.
이를 위해서 복구하기 전 먼저 현재 가리키고 있는 Segment Tree 상의 Index가 기존 배열에서 몇 번째 Index인지를 알아내야 한다.
(문제의 1번 예시에서 두 번째 Z가 수행된 뒤 파랑색 행 번호가 2에서 3으로 늘어난 경우)
그 후 복구에 사용된 실제 배열 상의 인덱스와 현재 Segment Tree 상의 Index가 기존 배열에서 가리키는 인덱스를 비교해서 만약 복구에 사용된 실제 배열 상의 인덱스가 더 작다면 복구한 뒤 현재 Segment Tree 상에서 가리키고 있는 Index를 증가시켜주면 된다.

세그먼트 트리 코드는 아래와 같다.

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

using namespace std;

int segment[1 << 25];
int idx[1 << 25];

int get_num(string str)
{
    string s;
    for(int j=2;j<str.size();j++) 
        s.push_back(str[j]);
    return stoi(s);
}

int init(int s, int e, int node)
{
    if(s == e) {
        idx[s] = node;
        segment[node] = 1;
        return 1;
    }
    
    int mid = (s + e) / 2;
    return segment[node] = init(s, mid, node * 2) + init(mid + 1, e, node * 2 + 1);
}
int update(int s, int e, int node, int index)
{
    segment[node]--;
    if(s == e) 
        return s;
    
    int mid = (s + e) / 2;
    if(index > segment[node * 2])
        return update(mid + 1, e, node * 2 + 1, index - segment[node * 2]);
    else
        return update(s, mid, node * 2, index);
}
int search(int s, int e, int node, int index)
{
    if(s == e) 
        return s;
    
    int mid = (s + e) / 2;
    if(index > segment[node * 2])
        return search(mid + 1, e, node * 2 + 1, index - segment[node * 2]);
    else
        return search(s, mid, node * 2, index);
}
void restore(int node)
{
    if(node == 1) {
        segment[node]++;
        return;
    }
    segment[node]++;
    restore(node / 2);
}
string solution(int n, int k, vector<string> cmd) {
    string answer = "";
    init(1, n, 1);
    
    stack<int> st;
    int pos = k + 1;
    for(int i=0;i<cmd.size();i++) {
        char command = cmd[i][0];
        if(command == 'Z' || command == 'C') {
            if(command == 'C') {
                int real_idx = update(1, n, 1, pos);
                st.push(real_idx);
                if(pos == segment[1] + 1)
                    pos--;
            } else {
                int restored_idx = st.top(); st.pop();
                int real_idx = search(1, n, 1, pos);
                restore(idx[restored_idx]);
                if(restored_idx < real_idx) 
                    pos++;
            }
        } else {
            int num = get_num(cmd[i]);
            if(command == 'U') 
                pos -= num;
            else 
                pos += num;
        }
    }
    
    for(int i=0;i<n;i++) {
        if(segment[idx[i + 1]]) 
            answer.push_back('O');
        else 
            answer.push_back('X');
    }
    return answer;
}