[백준] 1406번 - 에디터 (c++)

자료구조 기초 응용 문제이다.

나는 list로 문제를 풀었지만 stack 두개를 가지고도 문제를 풀 수 있다는 걸

다른사람의 풀이를 보고 깨달았다. 

 

커서를 기준으로 왼쪽과 오른쪽을 스택에 넣어 푼다는 점이 흥미로웠다.

간단하지만 은근히 자료구조를 잘 활용해야 풀 수 있다는 점에서 좋은 문제라고 생각했다.

 

 

< 문제 >

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

1406번: 에디터

 

 

 

< 내 풀이 >

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

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

 

 

 

< stack으로 푼 풀이 >

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    string s = "";
    cin >> s;
    stack<char> l;
    stack<char> r;
    
    for (int i = 0; i < s.size(); i++) 
        l.push(s[i]);
    
    int n;
    cin >> n;
    while (n--) {
        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;
}

개인적으로는 stack으로 푼 풀이가 더 좋은 것 같다.

stack의 특징을 잘 사용한 풀이라고 생각해서다.

이런식으로 자료구조를 잘 응용해야겠다고 생각했다.