210326 개발일지(109일차) - 알고리즘 문제풀이(feat. stack) 백준 1406번

문제는 아래와 같다.
아래 코드로 처음 작성했는데, 시간초과가 났다.

import sys

array=list(sys.stdin.readline().rstrip())
n=int(sys.stdin.readline().rstrip())
commands=[sys.stdin.readline().rstrip().split() for _ in range(n)]

index=len(array)

for command in commands :
    if command[0] == 'P':
        array.insert(index, command[1])
        index += 1
    elif command[0] == 'L':
        if index > 0 :
            index -= 1
    elif command[0] == 'D':
        if index < len(array) :
            index += 1
    elif command[0] == 'B':
        if index > 0 :
            del array[index-1]
            index -= 1

print(''.join(array))

시간복잡도를 O(n)보다 더 줄여야하는 문제였다. 해결 방법은 아래와 같이 생각하면 된다.
이렇게 생각하고, 아래와 같이 코드를 작성해서 완료했다.

import sys

array1=list(sys.stdin.readline().rstrip())
n=int(sys.stdin.readline().rstrip())
commands=[sys.stdin.readline().rstrip().split() for _ in range(n)]

array2=[]

for command in commands :
    if command[0] == 'P':
        array1.append(command[1])
    elif command[0] == 'L' and array1:
        array2.append(array1.pop())
    elif command[0] == 'D' and array2:
        array1.append(array2.pop())
    elif command[0] == 'B' and array1:
        array1.pop()

print(''.join(array1 + list(reversed(array2))))