[백준 알고리즘/Python3] 1406 에디터

문제 이해 

백준에서 파이썬으로 하면 시간 초과가 잘걸리는거 같습니다. 처음에 cursor를 구현해서 list를 통해서 pop(), insert()연산을 했더니 시간초과가 떳습니다. 왜이러지 하고 검색해본 결과 O(n)시간이 걸려서 초과가 된거였습니다.

 

 

해결방법을 알아보니 2개의 스택을 이용하는 것입니다. "왼쪽스택", "오른쪽스택" 이라고 하겠습니다.

• 먼저 주어진 문장을 왼쪽스택에 넣습니다.
• 왼쪽으로 커서를 옮긴다면 왼쪽스택에 있는것이 오른쪽 스택으로 갑니다.
• 오른쪽으로 커서를 옮긴다면 오른쪽스택에 있는것이 왼쪽 스택으로 갑니다.
• 문자를 지우려면 왼쪽 스택에 있는 top을 지우면 커서 왼쪽에 있는 것을 지우는 것과 같습니다.
• 커서 왼쪽에 문자를 추가하려면 왼쪽스택 top에 추가하는 것과 같습니다.

 

왼쪽,오른쪽 스택은 커서를 기준으로 나뉘여 집니다.

커서를 기준으로 본다면 왼쪽 스택의 top 이후는 오른쪽스택의 바닥 입니다. 그래서 출력할 때 왼쪽스택을 쭉 출력하고 오른쪽 스택의 반대부터 출력하면 됩니다.

 

코드

 

import sys
left_stack = list(input())
test_case = int(input())
right_stack = []

cursur = len(left_stack)
for i in range(test_case):
    command = sys.stdin.readline().split()

    if(command[0] == 'L'):
        if(left_stack != []):
            right_stack.append(left_stack.pop())

    if(command[0] == 'D'):
        if(right_stack != []):
            left_stack.append(right_stack.pop())

    if(command[0] == 'B'):
        if(left_stack):
            left_stack.pop()

    if(command[0] == 'P'):
        left_stack.append(command[1])

print(''.join(left_stack),end='')
print(''.join(list(reversed(right_stack))),end='')

왼쪽 오른쪽으로 움직일 때 스택이 비어있으면 넘어가게 끔 합니다. 지울 때도 왼쪽 스택에 값이 아무것도 없다면 넘어갑니다.

 

input()으로 받으면 시간초과가 납니다.