[백준] 1406: 에디터 (Python)

문제📖

풀이🙏

• 첫번째 시도에서는 시간복잡도를 고려하지 않고 했다.

import sys
data = list(input())
index = len(data)

for _ in range(int(input())):
    command = input().split()
    if command[0] == "P":
        data.insert(index, command[1])
        index += 1
    elif command[0] == "L":
        if index == 0:
            continue
        else:
            index -= 1
    elif command[0] == "B":
        if index == 0:
            continue
        del data[index-1]
        index -= 1
    elif command[0] == "D":
        if index >= len(data):
            continue
        index += 1

print("".join(data))

결과는 당연히 시간초과를 받았다.

• 그래서 두번째로 시간복잡도가 O(1)이면서 구현할 수 있는 방법을 생각했다. (list의 append, pop은 시간복잡도가 O(1)이다
  방법은 stack1과 stack2을 사용하여 커서의 위치에 따라 스택의 값을 수정하는 방법이다.
  즉, 커서 기준 왼쪽은 stack1에 오른쪽은 stack2에 저장한다.
• 출력을 위해서는 stack2는 순서를 반대로 하여 출력한다.

코드💻

import sys
input = sys.stdin.readline
stack1 = list(input().strip())
stack2 = []

for _ in range(int(input())):
    command = input().split()
    if command[0] == "P":
        stack1.append(command[1])
    elif command[0] == "L" and len(stack1) != 0:
        stack2.append(stack1.pop())
    elif command[0] == "D" and len(stack2) != 0:
        stack1.append(stack2.pop())
    elif command[0] == "B" and len(stack1) != 0:
        stack1.pop()

print("".join(stack1 + list(reversed(stack2))))