[프로그래머스/Level 3/C++/2021 카카오 채용연계형 인터십] 표 편집

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

- 출처 : 프로그래머스 코딩 테스트 연습

프로그래머스

 

[문제 요약]

- 위 그림에서 파란색으로 칠해진 칸은 현재 선택된 행을 나타냅니다. 단, 한 번에 한 행만 선택할 수 있으며, 표의 범위(0행 ~ 마지막 행)를 벗어날 수 없습니다. 이때, 다음과 같은 명령어를 이용하여 표를 편집합니다.

• "U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다.
• "D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다.
• "C" : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다.
• "Z" : 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.

- 이때, 최종 표의 상태와 처음 주어진 표의 상태를 비교하여 삭제되지 않은 행은 "O", 삭제된 행은 "X"로 표시하면 다음과 같습니다.

- 처음 표의 행 개수를 나타내는 정수 n, 처음에 선택된 행의 위치를 나타내는 정수 k, 수행한 명령어들이 담긴 문자열 배열 cmd가 매개변수로 주어질 때, 모든 명령어를 수행한 후 표의 상태와 처음 주어진 표의 상태를 비교하여 삭제되지 않은 행은 O, 삭제된 행은 X로 표시하여 문자열 형태로 return 하도록 solution 함수를 완성해주세요.

 

[문제 조건]

• 5 ≤ n ≤ 1,000,000
• 0 ≤ k < n
• 1 ≤ cmd의 원소 개수 ≤ 200,000
  • cmd의 각 원소는 "U X", "D X", "C", "Z" 중 하나입니다.
  • X는 1 이상 300,000 이하인 자연수이며 0으로 시작하지 않습니다.
  • X가 나타내는 자연수에 ',' 는 주어지지 않습니다. 예를 들어 123,456의 경우 123456으로 주어집니다.
  • cmd에 등장하는 모든 X들의 값을 합친 결과가 1,000,000 이하인 경우만 입력으로 주어집니다.
  • 표의 모든 행을 제거하여, 행이 하나도 남지 않는 경우는 입력으로 주어지지 않습니다.
  • 본문에서 각 행이 제거되고 복구되는 과정을 보다 자연스럽게 보이기 위해 "이름" 열을 사용하였으나, "이름"열의 내용이 실제 문제를 푸는 과정에 필요하지는 않습니다. "이름"열에는 서로 다른 이름들이 중복없이 채워져 있다고 가정하고 문제를 해결해 주세요.
• 표의 범위를 벗어나는 이동은 입력으로 주어지지 않습니다.
• 원래대로 복구할 행이 없을 때(즉, 삭제된 행이 없을 때) "Z"가 명령어로 주어지는 경우는 없습니다.
• 정답은 표의 0행부터 n - 1행까지에 해당되는 O, X를 순서대로 이어붙인 문자열 형태로 return 해주세요.

정확성 테스트 케이스 제한 사항

• 5 ≤ n ≤ 1,000
• 1 ≤ cmd의 원소 개수 ≤ 1,000

효율성 테스트 케이스 제한 사항

• 주어진 조건 외 추가 제한사항 없습니다.

 

[문제 풀이]

필자는 처음에 자료들을 링크드 리스트의 형태로 자료들을 저장했다. 처음에 문제에서 U,D 연산에서 X의 값이 최대 30만이고 cmd의 원소개수가 20만개라 리스트로 하면 시간초과가 날 것으로 예상했으나 cmd에서 주어지는 모든 X값의 합이 100만을 넘지 않기 때문에 리스트로도 충분할 것 같았다.

 

이 문제에서 핵심이 되는 연산은 C와 Z연산이다.

 

Z연산에서 최근에 삭제된 행을 복구할때 필자는 자료구조 stack을 이용하여 복구를 진행했다. stack이 LIFO(Last In First Out)의 원리라 stack을 이용하여 복구를 했다.

 

근데 복구를 할때 중요했던 점이 C연산에서 하나의 행을 삭제할때 그 노드를 실제로 메모리를 해제시키는 것이 아니라 그 원소를 그대로 둔 체로 앞 뒤의 링크만 끊어지는 형식으로 냅둔 다음 Z연산으로 복구 시킬때는 다시 앞 뒤 원소와 링크를 연결해주는 방식으로 시간을 단축시켰다.

위와 같은 방식으로 주황색 노드를 남겨두는 방식으로 리스트를 유지시켰다.

 

이렇게 하면 stack에는 주황색 노드의 주소값이 들어가기 때문에 바로 노드에 접근할 수 있고, 양 옆 노드도 다시 접근이 가능하기 때문에 시간단축에 용이하다.

 

[소스 코드]

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

#define pii pair<int,int>

using namespace std;

typedef struct Node
{
    int num;
    struct Node *prev;
    struct Node *next;
}Node;

Node *new_node(int num)
{
    Node *n_node = (Node *)malloc(sizeof(Node));
    n_node->num = num;
    n_node->prev = n_node->next = NULL;
    return n_node;
}

Node *make_list(int n)
{
    Node *root;
    Node *cur;
    
    for(int i=0; i<n; i++)
    {
        Node *n_node = new_node(i);
        if(i==0) { root = n_node; cur = n_node; }  
        
        else
        {
            n_node->prev = cur;
            cur->next = n_node;
            cur = n_node;
        }
    }
    return root;
}

string solution(int n, int k, vector<string> cmd) {
    string answer = "";
    stack<Node *> stk;

    Node *root = make_list(n);
     
    Node *cur = root;
    for(int i=0; i<k; i++) cur=cur->next;

    for(int i=0; i<cmd.size(); i++)
    {
        char op = cmd[i].at(0);
        if(op == 'U')
        {
            int num;
            string tmp;
            for(int j=2; j<cmd[i].size(); j++) tmp.push_back(cmd[i].at(j));
            num = atoi(tmp.c_str());
            
            for(int m=0; m<num; m++)
            {
                 if(cur->prev==NULL) break;
                 cur=cur->prev;
            }
        }
        else if(op == 'D')
        {
            int num;
            string tmp;
            for(int j=2; j<cmd[i].size(); j++) tmp.push_back(cmd[i].at(j));
            num = atoi(tmp.c_str());
            
            for(int m=0; m<num; m++)
            {
                if(cur->next==NULL) break;
                cur=cur->next;
            }
        }
        else if(op == 'C')
        {
            if(cur == root)
            {
                stk.push(cur);
                root = cur->next;
                root->prev=NULL;
                cur=root;
            }
            else if(cur->next == NULL)
            {
                stk.push(cur);
                cur->prev->next = NULL; 
                cur = cur->prev;
            }
            else
            {
                stk.push(cur);
                cur->prev->next = cur->next;
                cur->next->prev = cur->prev;
                
                cur = cur->next;
            }
        }
        else if(op == 'Z')
        {
            Node *recover = stk.top(); stk.pop();
            if(recover->prev == NULL)
            {
                root->prev = recover;
                root=recover;
            }
            else if(recover->next==NULL)
            {
                recover->prev->next = recover;
            }
            else
            {
                recover->prev->next = recover;
                recover->next->prev = recover;
            } 
        }    
    }   

    Node *tmp = root;
    vector<bool> ck; ck.resize(n);
    while(tmp!=NULL)
    {
        ck[tmp->num] = true;
        tmp=tmp->next;
    }
    
    for(int i=0; i<n; i++)
    {
        if(ck[i]) answer.push_back('O');
        else answer.push_back('X');
    }
    
    return answer;
}

굳