[백준 1406] 에디터, C++

https://www.acmicpc.net/problem/1406

1406번: 에디터

 본 문제는 2004 Olympiad Croatian Highschool Competitions in Informatics National Competition #1 - Juniors 2번 문제다. 이 문제는 코드 플러스 알고리즘 기초 1/2 - 자료구조 1에 있는 문제다. (처음 이 문제를 접했을 때, C++ STL이 익숙하지 않아 못 풀었다. 내가 기초가 많이 부족하다고 느꼈던 여러 문제들 중 하나다.) 보통 list 또는 linked list로 접근할 것이다. 하지만 stack으로 문제를 해결 할 수 있다. (??? : 많은 사람들이 어떻게 stack으로 풀 생각을 했냐고 물어보는데 나도 stack으로 풀 생각을 못했다. 답을 찾아보고 알았다. - 2020. 01. 백준 오프라인 강의 중)

1. 커서를 기준으로 왼쪽 stack, 오른쪽 stack을 선언한다.
   
2. 문제 조건을 만족하면서, P일 경우 왼쪽 stack에 push
3. L일 경우, 왼쪽 stack top을 오른쪽 stack으로 push
4. R일 경우, 오른쪽 stack top을 왼쪽 stack으로 push
5. D일 경우, 왼쪽 stack top을 pop
6. 출력할 땐, 왼쪽 stack 전체를 오른쪽으로 push
7. 오른쪽 stack 전체를 pop하면서 출력

stack 소스 코드

#include <iostream>
#include <stack>
#include <string>
 
using namespace std;
 
int main() {
    string s = "";
    cin >> s;
    stack<char> l;
    stack<char> r;
    for (int i = 0; i < s.size(); i++) {
        l.push(s[i]);
    }
    int num;
    cin >> num;
    while (num--) {
        char tmp;
        cin >> tmp;
        if (tmp == 'P') {
            char c;
            cin >> c;
            l.push(c);
        }
        else if (tmp == 'L') {
            if (l.empty()) continue;
            else {
                r.push(l.top());
                l.pop();
            }
        }
        else if (tmp == 'B') {
            if (l.empty()) continue;
            else l.pop();
        }
        else if (tmp == 'D') {
            if (r.empty()) continue;
            else {
                l.push(r.top());
                r.pop();
            }
        }
    }
    while (!l.empty()) {
        r.push(l.top());
        l.pop();
    }
    while (!r.empty()) {
        cout << r.top();
        r.pop();
    }
    return 0;
}

 

list 소스 코드

#include <iostream>
#include <string>
#include <list>
 
using namespace std;
 
int main(){
    int n; 
    string s;
    cin >> s;
    cin >> n;
    list<char> l(s.begin(),s.end());  
    auto now = l.end();
    
    while(n--){ 
        char tmp;
        cin >> tmp;
        
        if(tmp == 'L'){
            if(now != l.begin()){
                now--;
            }
        } 
        else if(tmp == 'D'){
            if(now != l.end()){
                now++;
            }
        }
        else if(tmp == 'B'){
            if(now != l.begin()){
                now = l.erase(--now);
            }
        }
        else if(tmp == 'P'){
            char c;
            cin >> c;
            l.insert(now, c);
        }    
    }
    for (auto it = l.begin(); it != l.end(); it++) {
        cout << *it;
    }
    return 0;     
}