에디터

• 키로거과 거의 동일한 문제.
• 현재 위치에서의 삽입과 삭제, 그리고 현재 위치를 왼쪽이나 오른쪽으로 한칸씩 이동하는 연산이 필요하다.
• 이것들은 모두 링크드 리스트의 핵심 연산으로, 전부 O(1)에 가능하다.
• 그러나 기본 라이브러리에 링크드리스트가 제공되지 않는 파이썬에서, 링크드리스트를 새로 구현하기는 귀찮고, 대신 2개의 스택을 이용해서 동일한 연산들을 똑같이 O(1)에 처리할 수 있다. 연결 리스트 (Linked List) 참고.
• m개의 명령어를 모두 O(1)에 처리 가능하므로 총 시간복잡도는 O(m). 문자열을 처음 읽어서 초기화하고 마지막에 출력하는 것까지 시간복잡도에 포함한다면 문자열의 길이인 O(n)을 추가해서, O(n+m)이 된다.

"""Solution code for "BOJ 1406. 에디터".

- Problem link: https://www.acmicpc.net/problem/1406
- Solution link: http://www.teferi.net/ps/problems/boj/1406
"""

import sys


def main():
    text= sys.stdin.readline().rstrip()
    M = int(sys.stdin.readline())
    left = list(text)
    right = []
    for _ in range(M):
        match sys.stdin.readline().split():
            case ['L']:
                if left:
                    right.append(left.pop())
            case ['D']:
                if right:
                    left.append(right.pop())
            case ['B']:
                if left:
                    left.pop()
            case ['P', ch]:
                left.append(ch)

    print(''.join(left) + ''.join(reversed(right)))
    

if __name__ == '__main__':
    main()