백준 #1406 에디터 c++

 

백준 1406번 에디터 문제이다. 레벨은 실버3.

 

일단 분류가 알고리즘상 스택으로 분류가 되어있다.

 

하지만 스택으로 풀면 조금 귀찮은 부분이 없지 않고, 리스트로 풀면 가장 간단한데,

 

그 이유인 즉, 스택은 인덱스 수정을 하려면 그 과정이 복잡하지만

 

리스트는 중간 삽입이 손쉽게 가능하기 때문이다.

 

//list.insert(iter, k); 

//list.erase(iter);

 

리스트의 경우 위와 같은 코드를 활용해서 P $ 와 D 명령어를 쉽게 구현할 수 있다.

 

스택으로 구현하는 방법을 생각해보자.

 

스택은 특성상, Push를 할 경우 가장 위쪽에 추가가 되고, pop을 해도 가장 위쪽 값이 사라지며

 

값 반환 역시 가장 위에 있는 값 밖에 되지 않는다.

 

그렇기 때문에 기존의 스택 말고, 다른 스택을 정의해서 커서를 옮겨갈 때마다 임시 스택에 푸시하는 방법을 쓴다.

 

아래는 c++을 사용한 코드 전문이다.

 

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

using namespace std;
// L 이 들어오면 기존 스택에서 예비 스택으로 top을 옮김 ->기존스택이 empty인지 아닌지 검사
// D 가 들어오면 예비스택에서 기존스택으로 옮김 -> 예비 스택이 empty인지 아닌지 검사
// B 가 들어오면 기존 스택 pop; -> 기존 스택이 empty 이면 무시 -> 예비 스택은 그대로 있음
// P $ 가 들어오면 push 함.
//
//
//
//
string str;
stack<char> st;
stack<char> temp;

int main() {
    cin >> str;
    int n;
    for(int i = 0; i < str.length(); i++) {
        st.push(str[i]);
    }
    cin >> n;
    while(n--) {
        char command;
        cin >> command;
        if(command == 'P') {
            char c;
            cin >> c;
            st.push(c);
        }
        else if(command == 'L') {
            if(st.empty())
                continue;
            else {
                temp.push(st.top());
                st.pop();
            }
        }
        else if(command == 'B') {
            if(st.empty()){
                continue;
            }
            else {
                st.pop();
            }
        }
        else if(command == 'D') {
            if(temp.empty()) continue;
            else {
                st.push(temp.top());
                temp.pop();
            }
        }
    }
    while(!st.empty()) {
        temp.push(st.top());
        st.pop();
    }
    
    while(!temp.empty()) {
        cout << temp.top();
        temp.pop();
    }

    
    return 0;
    
}

 

마지막에는 임시배열에 푸시를 하면 역순으로 저장되고

 

다시 pop을 하면서 출력하면 원래 순서대로 출력된다.