[programmers] Lv.3 표 편집(c++)

교훈: 생각나는 아이디어가 있으면 그냥 하자..

 

boubly linked list를 만들면 되겠다 생각했는데.. 만들어져있는걸로 그냥 하자 싶어서 set으로 진행했으나

답은 맞는데 아무리 해도 효율성이 안돼서 그냥 doubly linked list를 만들기로 결정..

별로 어려운것도 아닌데 더 쉽고 좋은 방법 찾겠다고 시간만 낭비했다.. 라는 일기

 

doubly linked list(양방향으로 연결된 리스트)

https://jolly-note.tistory.com/32

linked list - 이중(doubly) 연결 리스트

 

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

using namespace std;

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

string solution(int n, int k, vector<string> cmd) {
    Node* table = new Node();
    // 0번째 node가 지워졌을 경우, 문제가 발생하므로 주의!
    Node* start_table = table;
    Node* cur = table;
    
    for(int i=1; i<n; i++){
        table->next = new Node(i, table, NULL);
        table = table->next;
    }

    for(int i=0; i<k; i++)
        cur = cur->next;
    
    stack<Node*> deleted;
    for(string c: cmd){
        switch(c[0]){
            case 'U':
                for(int i=0; i<stoi(c.substr(2)); i++)
                    cur = cur->prev;
                break;
            case 'D':
                for(int i=0; i<stoi(c.substr(2)); i++)
                    cur = cur->next;                
                break;
            case 'C':
                deleted.push(cur);
                if(cur->prev != NULL) (cur->prev)->next = cur->next;
                else start_table = start_table->next;
                if(cur->next != NULL) {
                    (cur->next)->prev = cur->prev;
                    cur = cur->next;
                } else cur = cur->prev;
                break;
            case 'Z':
                if(deleted.top()->prev != NULL) (deleted.top()->prev)->next = deleted.top();
                else start_table = deleted.top();
                if(deleted.top()->next != NULL) (deleted.top()->next)->prev = deleted.top();
                deleted.pop();
                break;
        }
    }
    
    string answer(n, 'X');
    while(start_table != NULL){
        answer[start_table->data] = 'O';
        start_table = start_table->next;
    }
    
    return answer;
}

---

문제

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

코딩테스트 연습 - 표 편집

728x90

---

[접근1]

doubly linked list에 쓰일 Node 만들기

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

---

[접근2]

table 과 선택된 행 초기화

선택된 행 을 따로 table 초기 위치에 두고, table 초기위치를 나중에 처음부터 돌 때 처음으로 돌아가기 위해서 한칸씩 이동해야하는 비효율적인(?) 행동을 하지 않기 위해서 따로 만들어서 할당해뒀다(start_table).

이때 문제 하나가 틀리게 됐는데, 맨 처음 node(node의 prev가 null인 node)가 지워질 경우 start_table의 위치도 바꿔줘야했다.

Node* table = new Node();
// 0번째 node가 지워졌을 경우, 문제가 발생하므로 주의!
Node* start_table = table;
Node* cur = table;

for(int i=1; i<n; i++){
    table->next = new Node(i, table, NULL);
    table = table->next;
}

for(int i=0; i<k; i++)
    cur = cur->next;

---

[접근3]

조건 수가 적어서 if else를 사용해도 좋지만 개인적으로 switch가 가독성이 좋아서 switch를 즐겨쓰는편.

지워지는 node의 주소를 저장하기 위해서 deleted라는 stack<Node*>을 생성, Node*을 저장하면 그 Node의 prev와 next가 같이 저장되기 때문에, 나중에 되돌릴 때 위치를 따로 찾을 필요 없어서 편하다👍

'U'와 'D'의 경우, 이동하는 숫자(substr과 stoi로 구함)만큼 prev 또는 next로 cur을 이동시키고

'C'의 경우, 지워지는 cur을 deleted에 저장 후, 앞의 node의 next를 다음 노드와 연결하고 다음 노드의 prev를 앞의 노드와 연결한다. 이때, 만약 지워지는 node의 앞이 NULL이면 맨 앞의 node라는것을 의미하므로 start_table을 다음 노드로 이동시킨다. cur을 다음 노드로 이동하는데, 만약 NULL이면 지워지는 노드가 끝 노드라는 의미이므로 전 노드로 이동시킨다.

'Z'의 경우, deleted의 맨 위의 노드에 저장된 prev 노드를 복구 시킬 노드의 next와 연결시켜주고, 저장된 next 노드의 prev 노드를 복구 시킬 노드와 연결시켜준다. 이때도 만약 복구 시킬 노드의 prev가 NULL이라면, 맨 앞의 node로 복구 된다는것을 의미하므로 start_table을 복구시키는 node로 이동시킨다. 그리고 deleted의 맨 위의 노드를 pop해준다.

stack<Node*> deleted;
for(string c: cmd){
    switch(c[0]){
        case 'U':
            for(int i=0; i<stoi(c.substr(2)); i++)
                cur = cur->prev;
            break;
        case 'D':
            for(int i=0; i<stoi(c.substr(2)); i++)
                cur = cur->next;                
            break;
        case 'C':
            deleted.push(cur);
            if(cur->prev != NULL) (cur->prev)->next = cur->next;
            else start_table = start_table->next;
            if(cur->next != NULL) {
                (cur->next)->prev = cur->prev;
                cur = cur->next;
            } else cur = cur->prev;
            break;
        case 'Z':
            if(deleted.top()->prev != NULL) (deleted.top()->prev)->next = deleted.top();
            else start_table = deleted.top();
            if(deleted.top()->next != NULL) (deleted.top()->next)->prev = deleted.top();
            deleted.pop();
            break;
    }
}

---

[접근4]

정답을 'X' character n개로 이루어진 string으로 초기화해주고, start_table 위치부터 시작하여 NULL이 될때까지 돌면서 node의 data를 index로 사용하여 answer의 해당 부분을 'O'로 바꿔준다.

string answer(n, 'X');
while(start_table != NULL){
    answer[start_table->data] = 'O';
    start_table = start_table->next;
}

return answer;