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

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/81303

코딩테스트 연습 - 표 편집

1. 주의할 점

- 어렵다... 많이 어렵다(이전 인턴 문제에 비해 난이도가 급 상승했다)

- 세그먼트 트리 or 리스트 or STL에 대한 이해도가 높은 해결 할 수 있다

 

2. 구현

- 세그먼트 트리 or 리스트로는 아직 풀어보지 않아서 Set을 통해 해결했다(조만간 세그먼트 트리, 리스트로도 풀어 볼 예정)

- Set과 Set의 Iterator 속성을 잘 이용한다. C++에서 일반적으로 사용하는 Set은 정렬이다(정렬X → UnorderedSet)

※ Iterator란?

포인터 형태로, '현재 Set에서 가리키고 있는 곳'이라고 생각하면 된다

iterator++ : 다음 원소를 가리킨다

--iterator: 이전 원소를 가리킨다

 

- it++를 통해 D를 표현한다

- it--를 통해 U를 표현한다

- Stack+Set의 성질을 통해 Z를 표현한다(Stack을 통해 최근에 삭제한 원소 불러온다 + Set은 자동정렬의 성질을 지닌다)

- Iterator의 erase기능을 통해 C를 표현한다. 임시 Iterator인 Temp를 통해 삭제 이후 조건에 맞춰서 it의 위치를 수정해준다

- 출력할 때, 0~N-1까지의 값과 Set의 값을 비교하여 Answer에 할당한다. 이때, 여러가지 방법이 존재하지만 아래와 같이 구현할 경우, "OOOXX"와 같이 뒤가 연속된 X로 이루어질 경우 표현이 안되므로 idx가 N이 될 때까지 While문을 추가 수행한다

#include <string>
#include <vector>
#include <iostream>
#include <set>
#include <stack>
using namespace std;
set<int> s;

string solution(int n, int k, vector<string> cmd) {
    string answer = "";
    for(int i=0;i<n;i++)
        s.insert(i);
    set<int> :: iterator it,temp;
    it = s.begin();
    while(k--){
        it++;
    }
    stack<int> st;
    for(int i=0;i<cmd.size();i++){
        string str = cmd[i];
        char c = str[0];
        if(c=='C' || c=='Z'){
            if(c=='C'){
                st.push(*it);
                temp = it;
                temp++;
                if(temp==s.end()){
                    temp = it;
                    --temp;
                }
                s.erase(it);
                it = temp;
            }
            else{
                s.insert(st.top());
                st.pop();
            }
        }
        else{
            string ss = str.substr(2);
            int val = stoi(ss);
            while(val--){
                if(c=='D')  ++it;
                else    --it;
            }
        }
    }
    
    int idx=0;
    for(it = s.begin();it!=s.end();it++){
        int val = *it;
        if(val==idx){
            answer+='O';
        } 
        else{
            while(idx<val){
                answer+='X';
                idx++;
            }
            answer+='O';
        }
        idx++;
    }
    while(idx<n){		//"OOOXX" 같은 예외 잡아주기 위함
        answer+='X';
        idx++;
    }
    return answer;
}