문제 접근 방식

먼저 문자열을 다루는 문제였기 때문에 C++ 대신 Python으로 푸는게 편해 Python으로 풀이하였다.

그리고 처음 봤을 때는 어..? 그냥 구현만 하면 되는거 아닌가? 해서 무식하게 구현해봤다. 커서를 움직이며 문자열 슬라이싱을 이용해 구현했는데 시간초과가 났다.

생각해보면 문자열의 최대 길이가 600,000글자이고 명령어의 개수는 최대 500,000개이기 때문에 무식하게 구현하면 시간초과가 발생할 수 밖에 없는 문제였다.

계속 어떻게 하지 고민하다가 자료구조 문제라는 힌트를 보고 스택으로 구현하면 되겠구나! 라고 생각했다.

커서를 기준으로 왼쪽에 있는 문자열과 오른쪽에 있는 문자열로 나눈다.

예를 들어 "abcdef"라는 문자열이 있고 커서가 c와 d사이에 있다고 가정해보자. 이 때 left, right 스택은 다음과 같다.

여기서 명령어에 따라 적절하게 stack값을 변경해준다.

L명령어 : left의 마지막 원소를 right로 옮김 (left가 비어있으면 실행X)
D명령어 : right의 마지막 원소를 left로 옮김 (right가 비어있으면 실행X)
B명령어 : left의 마지막 원소를 삭제함 (left가 비어있으면 실행X)
P명령어 : left에 입력받은 문자를 추가함

이렇게 하면 cursor를 매번 움직이며 수행하는 것보다 훨씬 간결하고 빠르게 수행할 수 있게 된다.

명령어 수행이 끝나면 left와 right를 합쳐줘야 하는데 right는 순서가 거꾸로 들어간다는 것을 고려해 reversed(right)를 사용하여 합쳐주었다.

최종 코드

import sys

left = list(sys.stdin.readline().rstrip())
right = []

for _ in range(int(sys.stdin.readline())):
    line = list(sys.stdin.readline())

    if line[0] == 'L':
        if left:
            right.append(left.pop())
    elif line[0] == 'D':
        if right:
            left.append(right.pop())
    elif line[0] == 'B':
        if left:
            left.pop()
    else:
        left.append(line[2])

answer = ''.join(c for c in left) + ''.join(c for c in reversed(right))
print(answer)

결과