1406 에디터

1406. 에디터 / c++ / Silver2 / 25분

문제

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

1. 에디터에는 다음과 같은 명령이 주어진다.
   1. L : 현재 커서의 위치를 왼쪽으로 한칸 옮기기 (가장 왼편일 경우 무시)
   2. D : 현재 커서의 위치를 오른쪽으로 한칸 옮기기 (가장 오른편일 경우 무시)
   3. B : 현재 커서의 왼쪽 문자를 삭제 (가장 왼편일 경우 무시) (오른쪽 문자는 그대로이고, 커서는 왼편으로 당겨짐)
   4. P : 현재 커서의 왼쪽에 문자를 삽입

접근 방식

자료구조, 스택

1. 처음엔 string으로 풀어야 하나 했다.
2. 잘 생각해보니 커서를 기준으로 왼쪽과 오른쪽을 나눠서 자료구조에 삽입 삭제가 일어나는 것을 파악했다.
3. 왼쪽을 스택, 오른쪽을 큐로 풀어봤다.
4. 멍청했다. (항상 그림판이나 메모장으로 시뮬레이션을 돌려봐야한다.)
5. 양쪽 다 스택으로 하고, 마지막에 왼쪽 스택에서 뽑은 문자열을 한번 뒤집어 준 후, 오른쪽 스택에서 뽑은 문자열을 더해주어서 풀었다.

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;

string str;
int orderCnt;
char order1, order2;
stack<char> leftS, rightS;

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

    cin >> str;
    for (int i = 0; i < str.length(); ++i)
    {
        leftS.push(str[i]);
    }
    cin >> orderCnt;
    while (orderCnt-- > 0)
    {
        cin >> order1;
        switch (order1)
        {
        case 'L':
            if (leftS.size() > 0)
            {
                rightS.push(leftS.top());
                leftS.pop();
            }
            break;
        case 'D':
            if (rightS.size() > 0)
            {
                leftS.push(rightS.top());
                rightS.pop();
            }
            break;
        case 'B':
            if (leftS.size() > 0)
            {
                leftS.pop();
            }
            break;
        case 'P':
            cin >> order2;
            leftS.push(order2);
            break;
        }
    }

    str = "";

    while (!leftS.empty())
    {
        str += leftS.top(); leftS.pop();
    }
    reverse(str.begin(), str.end());
    while (!rightS.empty())
    {
        str += rightS.top(); rightS.pop();
    }

    cout << str << '\n';

    return 0;
}

다시 생각해 볼 점

1. 좌우로 연결되어 있고, 그 사이에 삽입 삭제가 일어난다면, ‘이중 연결 리스트’를 생각해봐야 한다.
2. 이 경우는 커서 기준으로 나눠서 왼쪽 오른쪽 문자열을 스택으로 처리한게 중요했다.