백준 - (# 1406)

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

Code 1

from sys import stdin
s = stdin.readline().strip()
n = len(s)
m = int(input())
cursor = n-1

for i in range(m):
    cmd = stdin.readline().strip()
    if cmd[0] == 'L':
        if cursor != 0:
            cursor += -1

    elif cmd[0] == 'D':
        if cursor != n:
            cursor += 1

    elif cmd[0] == 'B':
        if n != 0:
            s = s[:cursor] + s[cursor+1:]
            n += -1
            cursor += -1

    elif cmd[0] == 'P':
        s = s[:cursor+1] + cmd[2] + s[cursor+1:]
        n += 1
        cursor += 1

print(s)

Code 2

from sys import stdin
left_s = list(stdin.readline().strip())
right_s = []
m = int(input())
for i in range(m):
    cmd = stdin.readline().strip()
    if cmd[0] == 'L':
        if left_s:
            right_s.append(left_s.pop())
        
    elif cmd[0] == 'D':
        if right_s:
            left_s.append(right_s.pop())

    elif cmd[0] == 'B':
        if left_s:
            left_s.pop()

    elif cmd[0] == 'P':
        left_s.append(cmd[2])

right_s.reverse()
result = left_s + right_s
print(''.join(result))

참고

Code 1은 시간 초과가 나온다. 하나의 리스트나 문자열로 구현할 경우 배열의 부분을 가져오거나 삽입 또는 제거를 하기 위해 O(N)이 필요하다.
Code 2 처럼 커서 위치를 기준으로 두 개의 리스트(스택)로 나누어 pop()과 append()를 사용하면 O(1)으로 가능하다.