[백준] 1406번 : 에디터

문제

 

---

풀이

 

이 문제의 핵심은 커서 위치 정보를 따로 저장하지 않은 채 문제를 푸는 것이다.

그러려면 스택을 2개 사용해야 한다.

 

s1에 입력을 char 단위로 쪼개어 넣었다.

 

커서는 처음에 문장 맨 뒤에 위치한다. 이때 커서의 왼쪽 문자는 d고 이는 s1.top과 일치한다.

그럼 각 명령에 대해 해야할 일은 무엇일까?

 

L

d를 가리키던 커서가 c를 가리키도록 해야한다. s1.top이 c가 되기 위해선 d가 없어져야 한다.

하지만 d를 완전히 없앨 수는 없다. 그래서 d를 s2에 옮겨준다.

 

D

c를 가리키던 커서가 다시 d를 가리키도록 해야한다. 그럼 s1.top이 다시 d가 되어야 한다는 것이다.

s2.top에 있던 d를 다시 s1으로 옮겨온다.

 

B

현재 커서의 왼쪽 문자를 지워야 한다. 이는 s1.top인 d가 된다. 그래서 그냥 s1.pop을 한다.

 

P

현재 커서의 왼쪽에 문자를 추가하고, 이 투입된 문자의 오른쪽에 커서가 위치하도록 해야한다.

s1.push로 값을 넣어준다. x를 넣는다고 치면

이렇게 된다.

 

그럼 결과를 어떻게 출력할까?

예제 입력 1에 대해 위와 같은 작업을 하면

이렇게 된다. 당장 이 구조에서는 와닿지 않겠지만

답을 출력할 때는 s1을 출력하고 s2를 출력해야 하는데 s1는 역순으로, s2는 그대로 출력하면 된다.

그래서 s1을 다시 하나하나 s2에 넣어준다.

 

s2를 출력하면 abcdyx가 나올 것이다.

---

소스코드

 

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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    string input;
    stack<char> s1, s2, s3;
    int M;
    char command, input_char, tmp;

    cin >> input;
    for (int i = 0; i < input.size(); i++)
        s1.push(input[i]);
    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> command;
        switch (command) {
            case 'L': //s1의 top을 s2에 push
                if (!s1.empty()) {
                    tmp = s1.top();
                    s1.pop();
                    s2.push(tmp);
                }
                break;
            case 'D': //s2의 top을 s1에 push
                if (!s2.empty()) {
                    tmp = s2.top();
                    s2.pop();
                    s1.push(tmp);
                }
                break;
            case 'B': //s1의 top 삭제
                if (!s1.empty())
                    s1.pop();
                break;
            case 'P': //s1에 push
                cin >> input_char;
                s1.push(input_char);
                break;
        }
    }
    while (!s1.empty()) {
        s3.push(s1.top());
        s1.pop();
    }
    while (!s3.empty()) { //s1은 뒤집어서 출력
        cout << s3.top();
        s3.pop();
    }
    while (!s2.empty()) { //s2는 그대로 출력
        cout << s2.top();
        s2.pop();
    }
}