[C++] Programmers 표 편집

문제 설명

 

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

 

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

프로그래머스

---

내 풀이 과정

첫 번째 시도

처음에 생각한 방법은 삭제되었는 지를 체크하는 bool 배열을 사용하여, 정확한 값을 저장하려고 하였다.

하지만 그렇게 풀기에는 너무 쉬워서 링크 리스트로 구현하면 좀 더 문제가 의도한 바에 일치하지 않나라는 생각을 하였다.

 

그래서 Record라는 배열에 현재 값, 이전 값, 다음 값을 저장 후 4가지 명령어에 따라 작동하도록 하였다.

 

 

첫 번째 코드

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

using namespace std;
const int max_size = 1000010;

struct Record {
    int val;
    int prev;
    int next;
};
Record record[max_size];
stack <Record> deleted;
int now_record, record_count;

void setting(int n) {    
    for(int i = 0; i < n; ++i) {
        record[i].val = i;
        record[i].prev = (i == 0 ? i : i - 1);
        record[i].next = (i == n - 1 ? i : i + 1);
    }
}

void do_up(int n) {
    while(n--) now_record = record[now_record].prev;
}

void do_down(int n) {
    while(n--) now_record = record[now_record].next;
}

void do_delete() {
    int prev = record[now_record].prev;
    int next = record[now_record].next;
    deleted.push(record[now_record]);
    
    record[prev].next = next;
    record[next].prev = prev;
    
    now_record = (next != record_count - 1 ? next : prev);
}

void do_recover() {
    Record target = deleted.top();
    deleted.pop();
    
    int val = target.val;
    int prev = target.prev;
    int next = target.next;
    
    record[prev].next = val;
    record[next].prev = val;
}

void do_cmd(string cmd) {
    if(cmd.at(0) == 'U') do_up(stoi(cmd.substr(2)));
    if(cmd.at(0) == 'D') do_down(stoi(cmd.substr(2)));
    if(cmd.at(0) == 'C') do_delete();
    if(cmd.at(0) == 'Z') do_recover();
}

string solution(int n, int k, vector<string> cmd) {
    string answer = "";
    now_record = k;
    record_count = n;
    
    for(int i = 0; i < n; ++i) answer += "O";
    
    setting(n);
    int cmd_size = cmd.size();
    for(int i = 0; i < cmd_size; ++i) do_cmd(cmd.at(i));
    
    while(!deleted.empty()) {
        Record target = deleted.top();
        deleted.pop();
        
        answer[target.val] = 'X';
    }
    
    return answer;
}

 

 

첫 번째 결과

(어머나)

 

그런데 틀렸다.

뭐가 틀렸는 지 고민하고 새로운 테스트 케이스를 넣어보았는데..

 

 

---

두 번째 시도

기존 코드에서는 0번째 record의 prev와 n - 1번째 record의 next가 각각 0과 n - 1로 저장하게 하였다.

하지만 이렇게 하다보니 0번째나 n - 1번째 record를 삭제하는 명령어가 진행되면, 인접한 record에 그대로 저장이 되는 현상이 발생하였다.

그래서 이를 해결하기 위해 out_of_range라는 상수를 만들어, 끝에 위치하는 record에 저장하였다.

뿐만 아니라, 명령어를 수행 후, 인접한 record의 prev와 next를 갱신할 때, out_of_range값이 포함되어 있다면 따로 갱신하지 않도록 하였다.

 

 

 

두 번째 코드

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

using namespace std;
const int max_size = 1000010;
const int out_of_range = 987654321;

struct Record {
    int val;
    int prev;
    int next;
};
Record record[max_size];
stack <Record> deleted;
int now_record;

void setting(int n) {    
    for(int i = 0; i < n; ++i) {
        record[i].val = i;
        record[i].prev = (i == 0 ? out_of_range : i - 1);
        record[i].next = (i == n - 1 ? out_of_range : i + 1);
    }
}

void do_up(int n) {
    while(n--) now_record = record[now_record].prev;
}

void do_down(int n) {
    while(n--) now_record = record[now_record].next;
}

void do_delete() {
    int prev = record[now_record].prev;
    int next = record[now_record].next;
    deleted.push(record[now_record]);
    
    if(prev != out_of_range) record[prev].next = next;
    if(next != out_of_range) record[next].prev = prev;
    
    now_record = (next != out_of_range ? next : prev);
}

void do_recover() {
    Record target = deleted.top();
    deleted.pop();
    
    int val = target.val;
    int prev = target.prev;
    int next = target.next;
    
    if(prev != out_of_range) record[prev].next = val;
    if(next != out_of_range) record[next].prev = val;
}

void do_cmd(string cmd) {
    if(cmd.at(0) == 'U') do_up(stoi(cmd.substr(2)));
    if(cmd.at(0) == 'D') do_down(stoi(cmd.substr(2)));
    if(cmd.at(0) == 'C') do_delete();
    if(cmd.at(0) == 'Z') do_recover();
}

string solution(int n, int k, vector<string> cmd) {
    string answer = "";
    now_record = k;
    
    for(int i = 0; i < n; ++i) answer += "O";
    
    setting(n);
    int cmd_size = cmd.size();
    for(int i = 0; i < cmd_size; ++i) do_cmd(cmd.at(i));
    
    while(!deleted.empty()) {
        Record target = deleted.top();
        deleted.pop();
        
        answer[target.val] = 'X';
    }
    
    return answer;
}

 

두 번째 결과

 

찢었다

---

다른 사람 코드

 

다른 분들도 거의 모두 링크 리스트를 사용하여 풀었다.

함수 분리, 세세한 구현 사항들은 달랐지만, 로직 자체는 내 시도와 매우 흡사하였다.

그 중 개인적으로 더 깔끔하다 싶었던 구현 방법이 있었는데

typedef struct Node {
    int row;
    bool live;
    Node *next;
    Node *prev;
} Node;

Node nodes[1000000], *now;

 

바로 이 코드였다.

나는 현재 몇 번째 record를 다루고 있는 지를 now_count라는 변수에 저장하였는 데, 이 분은 *now라는 포인터를 사용하였다.

확실히 내 코드보다는 좀 더 직관적이고, c++을 더 잘 활용하신 것 같다.