greentea31's Note

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

풀이 과정

알파벳 대문자, 소문자, 숫자, 백스페이스, 화살표를 인식해서 사용자가 입력한 단어가 무엇인지 출력하는 문제이다.

현재 커서의 위치에 따라 알파벳이 추가되는 위치, 삭제되는 위치가 결정된다. 배열로 문자열을 다룬다면 커서의 위치가 문장의 중간일 때 문자의 생성, 삭제 연산이 O(N)이 되어 비효율적인 코드가 된다. 생성, 삭제 연산을 O(1)로 만들어 줘야 한다.

1. 현재 커서의 위치를 2개의 스택으로 표현하기

커서 왼쪽에 있는 문자들을 1번 스택, 커서 오른쪽에 있는 문자들을 2번 스택에 저장한다고 하자. 그렇다면 문자의 삽입은 1번 스택에 push 연산을 해주는 것과 같으므로 O(1), 문자의 삭제는 1번 스택에 pop 연산을 해주는 것과 같으므로 O(1)이다. 화살표 입력시 1번 스택과 2번 스택의 top 요소들을 바꿔가면서 커서 왼쪽 문자, 커서 오른쪽 문자들을 유지해주면 된다.

모든 입력을 받았으면, 2번 스택의 요소들을 1번 스택에 전부 옮기면 모든 문자가 s1에 저장되게 된다. 이를 출력하면 되는데, s1에 있는 것을 그대로 출력시 문자열이 거꾸로 출력되므로 s2에 다시 옮겨담은 후 출력해주어야 원하는 문자열을 얻을 수 있다.

2. 링크드 리스트로 문자열을 표현하기

링크드 리스트에서는 삽입, 삭제 연산이 O(1)에 이루어지므로 효율적으로 커서의 위치에서의 삽입, 삭제 연산을 수행할 수 있다.

소스 코드

스택

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T--) {
        stack<char> s1;
        stack<char> s2;
        string L;
        cin >> L;
        for (char letter : L) {
            if (letter == '<') {
                if (s1.empty()) continue;
                s2.push(s1.top());
                s1.pop();
            } else if (letter == '>') {
                if (s2.empty()) continue;
                s1.push(s2.top());
                s2.pop();
            } else if (letter == '-') {
                if (s1.empty()) continue;
                s1.pop();
            } else {
                s1.push(letter);
            }
        }

        while(!s2.empty()) {
            s1.push(s2.top());
            s2.pop();
        }

        while(!s1.empty()) {
            s2.push(s1.top());
            s1.pop();
        }

        while(!s2.empty()) {
            cout << s2.top();
            s2.pop();
        }

        cout << '\n';
    }

    return 0;
}