[프로그래머스] 2021 카카오 채용연계형 인턴십 : 표 편집 (C++)

문제 링크 : 표 편집

참고, 참고

[문제 접근]

배열을 이용해서 풀면 정확성은 쉽게 맞출 수 있지만 효율성 테스트에서 점수를 얻지 못한다.
그래서 원래는 연결리스트를 구현해서 풀려고 했지만 생각처럼 잘 구현이 되지 않아서 다른 코드를 참고 했다.

이 분은 Set을 이용해서 풀었는데

• set 자료구조는 내부적으로 이진 트리 구조를 갖추고 있어서 삽입 / 삭제의 시간 복잡도가 O(logN) 이다.
• iterator를 통해 set의 원소에 순차적으로 접근할 수 있다.
• set 자료구조의 원소는 삽입과 동시에 정렬된다.

이 Set의 3가지 특징을 이용하면 이 문제를 쉽게 해결할 수 있다.
D = iterator++
U = iterator--
C = earse
Z = stack의 pop과 insert -> insert시 정렬되기 때문에 원래 있던 자리에 위치한다.

한가지 궁금증은

1번 코드

temp = it;
temp++;
// 마지막 행이면 위로
if(temp==row.end()) {
    temp = it;
    temp--;
}
row.erase(it);
it = temp;

2번 코드

temp = it;
// 마지막 행이면 위로
if(temp==row.end()) temp--;
else temp++;
row.erase(it);
it = temp;

1번 코드를 2번 코드로 변경하면 erase할 때 temp가 하나 더 내려간다.
즉, temp가 7일 때 마지막 행이면 temp가 6으로 변하고 row.earse(it)를 하면 temp가 5가 된다.

1번 코드는 earse시에도 제대로 6을 유지하는데 2번 코드는 왜 이러는지는 잘 모르겠다...
사실 temp는 주소값이 들어가 있기 때문에 엄밀히 말하자면 7이 아니라 7이 들어있는 메모리 주소값인데 이거와 관련이 있지 않을까 싶다..

[소스 코드]

#include <bits/stdc++.h>
using namespace std;

string solution(int n, int k, vector<string> cmd) {
    string answer = "";
    set<int> row;
    stack<int> st;
    
    for(int i=0 ; i<n ; i++) {
        row.insert(i);
    }
    set<int>::iterator it = row.begin(), temp; // temp는 삭제시 it위치를 위한 값
    while(k--) it++; // 시작점 찾기
    
    for(int i=0 ; i<cmd.size() ; i++) {
        if(cmd[i][0]=='D') {
            int dist = stoi(cmd[i].substr(2));
            while(dist--) it++;
        } else if(cmd[i][0]=='C') {
            st.push(*it);
            temp = it;
            temp++;
             // 마지막 행이면 위로
            if(temp==row.end()) {
                temp = it;
                temp--;
            }
            row.erase(it);
            it = temp;
        } else if(cmd[i][0]=='U') {
            int dist = stoi(cmd[i].substr(2));
            while(dist--) it--;
        } else if(cmd[i][0]=='Z') {
            row.insert(st.top());
            st.pop();
        }
    }
    
    int cnt=0;
    for(set<int>::iterator i = row.begin() ; i!=row.end() ; i++) {
        while(cnt!=*i) {
            answer+="X";
            cnt++;
        }
        answer+="O";
        cnt++;
    }
    for(int i=cnt ; i<n ; i++) { // X로 끝나는 경우 예외 처리
        answer+="X";
    }
    
    return answer;
}

Set STL을 잘 사용하면 더 좋은 코드참고

#include <bits/stdc++.h>
using namespace std;

string solution(int n, int k, vector<string> cmd) {
    string answer(n,'X');

    set<int> table;
    stack<int> hist;
    for(int i=0;i<n;i++) table.insert(i);

    auto cur = table.find(k);

    for(string s:cmd){
        if(s[0]=='U' || s[0]=='D'){
            int x = stoi(s.substr(2));
            if(s[0]=='U') while(x--) cur = prev(cur);
            else while(x--) cur = next(cur);
        }
        else if(s[0]=='C'){
            hist.push(*cur);
            cur = table.erase(cur);
            if(cur==table.end()) cur = prev(cur);
        }
        else if(s[0]=='Z'){
            table.insert(hist.top());
            hist.pop();
        }
        else return ""; // oops
    }

    for(int i:table) answer[i]='O';

    return answer;
}