프로그래머스(시뮬레이션, 카카오 기출; 표 편집) c++

#include <string>
#include <vector>
#include <stack>
using namespace std;

string solution(int n, int k, vector<string> cmd)
{
    vector<int> up(n + 2), down(n + 2);
    vector<bool> deleted(n, false);
    stack<int> deletedRows;
    
    // 실제 행은 1 ~ n, 0과 n+1은 더미 경계
    for(int i = 0; i <= n + 1; ++i)
    {
        up[i] = i - 1;
        down[i] = i + 1;
    }
    
    int cur = k + 1;   // k가 0-indexed였다면, 더미 때문에 +1 밀어줌
    
    for(string& command : cmd)
    {
        char op = command[0];
        int num = 0;
        if(op == 'U' || op == 'D')
            num = stoi(command.substr(2));
        
        if(op == 'U')
        {
            for(int i = 0; i < num; ++i)
                cur = up[cur];
        }
        else if(op == 'D')
        {
            for(int i = 0; i < num; ++i)
                cur = down[cur];
        }
        else if(op == 'C')
        {
            deleted[cur - 1] = true;   // deleted 배열은 원래 0-indexed 그대로 사용
            deletedRows.push(cur);
            
            up[down[cur]] = up[cur];
            down[up[cur]] = down[cur];
            
            // 삭제 후 커서: 아래가 진짜 행(더미가 아니면)이면 아래로, 아니면 위로
            if(down[cur] <= n)
                cur = down[cur];
            else
                cur = up[cur];
        }
        else if(op == 'Z')
        {
            int restore = deletedRows.top();
            deletedRows.pop();
            deleted[restore - 1] = false;
            
            up[down[restore]] = restore;
            down[up[restore]] = restore;
        }
    }
    
    string answer = "";
    for(int i = 0; i < n; ++i)
        answer += deleted[i] ? "X" : "O";
    return answer;
}

 

 

현재

행 번호:  0    1    2    3    4
up:      -1    0    1    2    3
down:     1    2    3    4    5

 

삭제

행 번호:  0    1    2(삭제됨)   3    4
up:      -1    0    1           1    3
down:     1    3    3           4    5

 

복구

up[down[restore]] = restore;    // 다시 원래대로 연결
down[up[restore]] = restore;

 

 

인덱싱이 깨지는 문제를 위해 더미를 추가.

배열 인덱스:   0(더미)   1    2    3    4    5    6(더미)
실제 의미:              행0  행1  행2  행3  행4

 

실제

인덱스:   0    1    2    3    4    5    6
up:      -1    0    1    2    3    4    5
down:     1    2    3    4    5    6    7