[프로그래머스/C++] 표 편집

문제

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

코딩테스트 연습 - 표 편집

풀이

bool형태의 idxs배열을 만들어서, 해당 행이 삭제되면 0, 존재하면 1로 판단하는 방식으로 구현해보았다.

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

using namespace std;

string solution(int n, int k, vector<string> cmd) {
    stack<int> removed;
    vector<bool> idxs(n,1); // 1:존재, 0:삭제됨
    int lastIdx = n-1;
    string answer = "";
    int tempIdx = k;
    for (auto c: cmd) {
        if (c[0] == 'U') {
            int num = stoi(c.substr(2,8));
            //cout << "num :" << num;
            int count = 0;
            while (count < num) {
                if (idxs[--tempIdx]) count++;
            }
        }
        if (c[0] == 'D') {
            int num = stoi(c.substr(2,8));
            int count = 0;
            while (count < num) {
                if (idxs[++tempIdx]) count++;
            }
        }
        if (c[0] == 'C') {
            idxs[tempIdx] = 0;
            removed.push(tempIdx);
            if (tempIdx == lastIdx) {
                lastIdx--; tempIdx--;
                continue;
            }
            while (true) {
                if (idxs[++tempIdx]) break;
            }
        }
        if (c[0] == 'Z') {
            int idx = removed.top();
            removed.pop();
            idxs[idx] = 1;
            if (idx > lastIdx) lastIdx=idx;
        }
    }
    for (int i=0;i<n;i++){
        if (idxs[i]) answer+='O';
        else answer+='X';
    }
    return answer;
}

흠.. 정확도에서 3개가 틀렸고, 효율성은 절반밖에 맞지못했다 ㅜㅜ

이 코드에서 정확도를 개선해봤자, 효율성에서 통과하지 못할 것 같아 다른 풀이 방법을 찾아보았다.

 

이 블로그의 풀이를 참고했다.

연결리스트를 사용하는 아이디어인데, C++에서 <set> 자료구조를 사용하면 훨씬 간단하게 구현이 가능했다.

 

연결리스트 대신에 set자료구조를 이용해도 되는 이유는 다음과 같다. (위 블로그 내용 발췌)

1. 이진트리 구조이다. → 삽입/삭제 시간 복잡도 : O(logN)
2. iterator를 통한 순차접근 가능→ next(), prev()를 통해 현재 원소의 양 옆 탐색 가능
3. set 내부의 원소들은 항상 정렬된 상태이다.

위 내용을 이해했다면 set 자료구조를 선언만 하면 자동으로 본 문제에서 요구하는 표 시스템이 구축됨을 알 수 있다! 기능에 따른 구현은 다음과 같이 할 수 있다.

커서 이동: next(set<int>::iterator), prev(set<int>::iterator)
행 삭제:    set<int>::erase(set<int>::iterator)
행 복원:    set<int>::insert(int)
심지어 erase()의 같은 경우, 원소 삭제 후 해당 원소의 다음 원소를 가리키는 iterator를 반환하므로 별 다른 구현없이 문제의 요구사항을 만족시킴을 알 수 있다. 삭제한 원소가 마지막 원소여서 iterator가 set<int>::end() 를 가리키게 될 경우에만 prev() 를 통해 이전 원소를 가리키게끔 예외 처리를 해주면 된다.

설명이 잘 적혀있어서, 이해하기가 쉬웠다. 

 

set을 이용한 코드는 아래와 같다.

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

using namespace std;

string solution(int n, int k, vector<string> cmd) {
    string answer(n,'X');
    stack<int> removed;
    set<int> table;
    for (int i=0;i<n;i++)
        table.insert(i);
    auto cur = table.find(k); // 현재 위치
    
    for(string c: cmd) {
        if (c[0] == 'U' || c[0] == 'D') {
            int num = stoi(c.substr(2));
            if (c[0] == 'U')
                while(num--)
                    cur = prev(cur);
            else
                while(num--)
                    cur = next(cur);
            continue;
        }
        if (c[0] == 'C') { // 삭제
            removed.push(*cur);
            cur = table.erase(cur);
            if (cur == table.end()) cur = prev(cur);
            continue;
        }
        if (c[0] == 'Z') { // 복구
            table.insert(removed.top());
            removed.pop();
            continue;
        }
    }
    for(int i:table) answer[i]='O';
    return answer;
}

결과

set을 이용한 코드로 100점을 받을 수 있었다. 다만, 실전에서 이런 문제를 받았을 때 set을 떠올릴 수 없었을 것 같다.

C++의 STL에 대한 이해도를 높여야겠다.