[Python] 1406 에디터 - 실버2

문제

풀이

# 에디터
import sys

input = sys.stdin.readline

l_stack = list(input().strip())

r_stack = list()
k = int(input())

for i in range(k):
    a = input()
    if a[0] == "P":
        l_stack.append(a[2])
        # cursor += 1
    elif a[0] == "L":
        if len(l_stack)==0:
            continue
        else:
            r_stack.append(l_stack.pop(-1))
    elif a[0] == "D":
        if len(r_stack)==0:
            continue
        else:
            l_stack.append(r_stack.pop(-1))
    elif a[0] == "B":   
        if len(l_stack)==0:
            continue
        else:
            l_stack.pop(-1)

for i in reversed(range(len(r_stack))):
    l_stack.append(r_stack[i])

print("".join(l_stack))

해석

처음 코드를 짰을 때는 아래와 같이 커서에 해당하는 부분을 변수로 넣고 짰다.

import sys

input = sys.stdin.readline

n = list(input())

k = int(input())


cursor = len(n)
for i in range(k):
    a = input()
    if a[0] == "P":
        n.insert(cursor, a[2])
        cursor += 1
    elif a[0] == "L":
        if cursor == 0:
            continue
        else:
            cursor -= 1
    elif a[0] == "D":
        if cursor == len(n):
            continue
        else:
            cursor += 1
    elif a[0] == "B":
        if cursor == 0:
            continue
        else:
            del n[cursor - 1]
            cursor -= 1

    if cursor < 0:
        cursor = 0
print("".join(n))

하지만 시간 초과가 됐다..

알아보니 insert연산에서 O(n)의 시간복잡도를 가지게 되어 시간초과가 발생한다고 한다..

커서 기준 왼쪽 스택과 오른쪽 스택을 구분해서 풀면 풀린다는 힌트를 얻고 그렇게 구현을 했더니 바로 풀렸다!!

2개의 스택으로 나누어서 풀었더니 풀리게 되었다.