[스택] 에디터 (백준 1406)(C++)

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

1406번: 에디터

 

1. 문제 개요

 

편집기가 지원하는 명령어가 다음과 같을 때, 초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 대, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 가정한다.

 

L	커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시)
D	커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시)
B	커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시)
P $	$이라는 문자를 커서 왼쪽에 추가함

 

 

2. 입출력

 

 

 

3. 문제 풀이

 

C++ string의 substring만을 사용하여 해결하려다 시간초과가 떴다. 검색해보니 Stack으로 풀 수 있는 문제였다.

아이디어는 다음과 같다.

a b | c d 

다음과 같이 있을 때, 커서의 왼쪽에 위치한 글자와 오른쪽에 위치한 글자로 나뉘어 스택에 저장하면 된다.

그러면 왼쪽 스택에는 (a,b)가 저장될 것이며 오른쪽 스택에는 (c,d)가 저장될 것이다.

 

이때 커서를 왼쪽으로 한 칸 옮긴다고 하면 왼쪽 스택의 탑에 있는 글자를 오른쪽으로 옮기면 된다. 그러면 (a), (b,c,d) 이렇게 될 것이다. 커서를 오른쪽으로 옮기는 것도 똑같이 수행하면 된다.

여기서 커서 왼쪽에 있는 문자를 삭제한다고 하면 왼쪽 스택의 탑에 있는 글자를 팝하면 되며, 커서 왼쪽에 문자열을 추가한다고 하면 왼쪽 스택에 푸쉬해주면 된다.

 

스택을 사용하면 빠르면서도 놀랍도록 간단하게 풀 수 있는 문제였다. 앞으로 시간적인 제약이 큰 문제에서는 스택을 바로 생각해보면 좋을 것 같다..

 

 

4. 전체 코드

 

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

using namespace std;

stack<char> l, r;

int main(void) {
    string str;
    cin >> str;
    
    for(int i=0;i<str.size();i++) l.push(str[i]);
    
    int n;
    cin >> n;
    
    for(int i=0;i<n;i++) {
        char temp;
        cin >> temp;
        if(temp=='L') {
            if(l.size()>0) {
                char top=l.top();
                l.pop();
                r.push(top);
            }
        } else if(temp=='D') {
            if(r.size()>0) {
                char top=r.top();
                r.pop();
                l.push(top);
            }
        } else if(temp=='B') {
            if(l.size()>0) l.pop();
        } else {
            char input;
            cin >> input;
            l.push(input);
        }
    }
    
    while(l.size()>0) {
        char top=l.top();
        l.pop();
        r.push(top);
    }
    
    while(r.size()>0) {
        char top=r.top();
        r.pop();
        cout << top;
    }
}

 

아직 배워가는 중이라 틀린 부분이 있을 수 있습니다. 지적할 부분이 있다면 댓글로 알려주시면 감사하겠습니다!!!