[프로그래머스 Lv3] : 표 편집

문제 링크

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

프로그래머스

 

표를 편집하기 위해 필요한 4가지 명령을 구현하는 문제.

 

풀이

• 처음 생각했던 아이디어

주어지는 명령어로는 커서의 위,아래 이동 , 해당 칸 삭제, 가장 최근에 삭제된 행 불러오기 이렇게 4가지가 있다.

삭제된 행을 다시 삽입하기 위해서 중간에 삽입하기가 편리한 덱을 이용해야겠다고 생각했다.

커서의 위치를 int로 두고, 주어진 숫자만큼 플러스 마이너스 연산을 이용해 커서의 이동을 구현했다.

 해당칸을 삭제할 때면 deq[k] 번째 인덱스를 (k는 커서 위치) 삭제하고 스택에 삭제한 인덱스에 대한 정보를 저장했다.

삭제된 행을 다시 불러올때는 스택의 맨위에 있는 행에 대한 정보를 꺼내서 덱에 다시 삽입하는 방식으로 했다.

 

위 방법으로 정확도테스트는 모두 통과했지만, 효율성 테스트에서 모두 시간초과를 받았다.

그래서 추가로 생각해낸 방법이

명령어를 펼쳐놓고 봤을 때, Z는 앞에는 항상 1개 이상의 C가 존재한다. C를 하고 Z를 하면 사실 두 명령어가 의미가 없어진다. 명령어로 Z가 들어오면 앞선 명령어중에 가장 가까운 명령어 C와 상쇄시키는 방법을 사용했다.

이게 답일 것이라고 생각했지만, 구현하기가 쉽지 않았고 계속 오류가났다.

 

• 참고한 아이디어

계속 안풀려서 다른 사람들은 어떻게 풀이를 했다 참고했다. 대부분의 사람들이 링크드 리스트를 이용했다고해서 나도 링크드 리스트를 이용했다.

링크드 리스트를 이용하면 좋은점

1. 행 삭제가 간편하다.

2. 삭제된 행을 복구하기에 최저화 되어있다.

연결리스트는 이전 행과, 다음 행에 대한 포인터를 가지고 있기때문에 다시 불러왔을 때

이전 행과 다음 행이 누구였는지를 바로 파악할 수 있다.

이전 행의 next와 다음 행의 prev를 복구시킬 행으로 바꿔주기만 하면 복구가 된다.

#include <bits/stdc++.h>
using namespace std;
 
struct Node{
    int val;
    Node* prev;
    Node* next;
    Node() {val = 0; prev = NULL; next = NULL;}
    Node(int t) { val = t; prev = NULL; next = NULL;}
};
 
string solution(int n, int k, vector<string> cmd) {
    string answer = "";
    Node* cursor = new Node(0);
    for(int i = 1; i<n; i++){
        cursor->next = new Node(i);
        cursor->next->prev = cursor;
        cursor = cursor->next;
    }
    for(int i = 0; i<n-k-1; i++)
        cursor = cursor->prev;
 
    stack<Node*> deleted;
    
    for(auto str : cmd){
        char command = str[0];
        if(command == 'U'){
            int cnt = stoi(str.substr(2));
            for(int i = 0; i<cnt; i++)
                cursor = cursor->prev;
        }
        else if(command == 'D'){
            int cnt = stoi(str.substr(2));
            for(int i = 0; i<cnt; i++)
                cursor = cursor->next;
        }
        else if(command == 'C'){
            deleted.push(cursor);
            if(cursor->next != NULL) cursor->next->prev = cursor->prev;
            if(cursor->prev != NULL) cursor->prev->next = cursor->next;
            if(cursor->next == NULL) cursor = cursor->prev;
            else cursor = cursor->next;
        }
        else if(command == 'Z'){
            Node* re = deleted.top();
            deleted.pop();
            if(re->next != NULL) re->next->prev = re;
            if(re->prev != NULL) re->prev->next = re;
        }
    }
    while(cursor->prev != NULL)
        cursor = cursor->prev;
    for(int i = 0; i<n; i++){
        if(cursor->val == i){
            answer += "O";
            if(cursor->next != NULL)
                cursor = cursor->next;
        }
        else
            answer += "X";
    }
    return answer;
}

 

내 방식대로 끝까지 풀어보려고했지만 결국 다수의 방법으로 풀게됐다.