[백준 1406] 에디터 문제

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

한 줄로 된 간단한 에디터 구현 문제이다.

편집기에는 커서가 존재하는데 커서는 문자열 어느곳에든 위치 할 수 있다.

즉, 길이가 L인 문자열이 있다면 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.

명령어 종류는...

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

처음에 문제를 봤을 때 무작정 문자열이라길래 배열로 처리를 할까 생각했다.

그치만 그렇게 된다면 문제가 존재했다. 바로 시간복잡도를 무시한 생각이었다.

배열로 문제를 풀게 된다면 추가, 삭제에 있어서 모든 문자열을 하나씩 다 미루고 당기고 해야하기 때문에

B, P연산에 대한 시간 복잡도는 각각 O(N)가 되며 그렇게 되면 총 시간 복잡도는 N^2가 되기 때문에 1초를 넘게된다.

다시 생각해보자.. 커서를 기준으로 숫자들을 나타낼 수 있는 알고리즘..

역시나 스택이다. 커서를 기준으로 왼쪽 문자열과 오른쪽 문자열을 나타내는 스택을 2개를 구현한다면 쉽게 가능하다.

이 경우 시간 복잡도는 B,P 연산에 대해서도 O(1)이 되므로 총 시간복잡도는 N 밖에 되지 않게 된다.

L 명령어에 대해서는 커서를 왼쪽으로 옮기겠다는 말은 왼쪽 스택의 top을 오른쪽 스택에 push 하고 왼쪽 스택에서 삭제.

R 명령어는 반대 케이스고.

B 명령어는 단지 왼쪽 스택에서 pop을 하면 된다.

P 명령어 또한 왼쪽 스택에 해당 문자를 push하면 되고.

소스코드는 다음과 같이 작성했다.

나는 결과값 출력을 위해 새로운 string에 왼쪽 스택의 내용을 담고 reverse하는 멍청한 짓을 했다.

더 쉬운 방법은 그냥 왼쪽 스택에 있는 내용물을 모두 오른쪽 스택에 몰아 담고 오른쪽 스택에서 하나씩 뽑아내며 출력을 하면 된다.

#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
 
using namespace std;
 
stack<char> L, R;
 
void opL() {
    // If cursor is leftmost, then ignore the operation.
    // This means L stack hasn't any elements in the stack.
    if (L.size() != 0) {
        char temp = L.top();
        L.pop();
        R.push(temp);
    }
}
 
void opD() {
    // If cursor is rightmost, then ignore the operation.
    // This means R stack hasn't any elements in the stack.
    if (R.size() != 0) {
        char temp = R.top();
        R.pop();
        L.push(temp);
    }
}
 
void opB() {
    // If cursor is leftmost, then ignore the operation.
    // This means L stack hasn't any elements in the stack.
    if (L.size() != 0) {
        L.pop();
    }
}
 
void opP(char a) {
    // Add character a into Left stack
    L.push(a);
}
 
void printStacks() {
    //이건 내가 짠거고 더 좋게 하려면
    //그냥 왼쪽 스택에 있는 애들 다 오른쪽으로 넘겨서
    // 오른쪽 스택만 출력하면 됨.
    string sentence = "";
    int size = L.size();
    for (int i = 0; i < size; i++) {
        sentence += L.top();
        L.pop();
    }
    //reverse the sentence for stack L.
    reverse(sentence.begin(), sentence.end()); 
    cout << sentence;
 
    //print stack R
    size = R.size();
    for (int i = 0; i < size; i++) {
        cout << R.top();
        R.pop();
    }
    cout << endl;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    int N;
    string s;
    char op, ch;
 
    cin >> s >> N;
 
    //initial state
    for (int i = 0; i < s.size(); i++)
        L.push(s.at(i));
 
    //operations
    for (int i = 0; i < N; i++) {
        cin >> op;
        switch (op) {
        case 'P':
            cin >> ch;
            opP(ch);
            break;
        case 'L':
            opL();
            break;
        case 'D':
            opD();
            break;
        case 'B':
            opB();
        }
    }
 
    //print the last sentence.
    printStacks();
    return 0;
}