[BOJ] [Python] 백준 자료구조 Stack - 1406: 에디터

문제: 1406-에디터

• 백준 1406 자료구조 
• Silver III
• 문제링크

1406번: 에디터

접근

이 문제는 풀기 전에 접근 방식을 엄청 고민했던 것 같다. 명령어들이 굉장히 직관적이기 때문에 그냥 list를 만들고 해당 인덱스에 insert하고 pop하는 방식으로 하면 되지 않을까? 했는데 시간 제한이 0.3초여서 시간 초과가 발생할 것 같아 스택을 사용하는 방법을 택했다. *insert와 pop은 O(n)의 시간 복잡도를 갖기 때문에 느린 편이다! *stack과 queue에서의 넣고 뺌은 시간 복잡도가 O(1)이다!

간단하게 설명하자면 커서를 기준으로 왼쪽, 오른쪽의 스택을 운영하고 커서가 움직일 떄마다 왼쪽의 스택과 오른쪽의 스택에서 원소를 주고받는다! 그러고 마지막에는 왼쪽 오른쪽의 스택을 합쳐준다. 커서가 가장 왼쪽 혹은 오른쪽으로 갔을 때는 커맨드를 무시하기 위해서 각 스택의 길이가 0이상일 때만 작업을 수행해주는 분기처리를 해주었다.

import sys

lst = sys.stdin.readline().strip()
N = int(sys.stdin.readline().strip())

left = []
right = []

for i in range(len(lst)):                               # 초기 뎈 생성
    left.append(lst[i])

for i in range(N):
    command = sys.stdin.readline().rstrip().split()    # 입력 값 파싱해서 받기
    if command[0] == "P":                              # P를 받았을 때 그 다음 문자를 왼쪽에 추가
        left.append(command[1])
    elif command[0] == "L":                             # L을 받았을 때
        if len(left):
            move = left.pop()                           # left의 마지막 element를 팝하고
            right.append(move)                          # right에 추가해준다
    elif command[0] == "D":                             # D를 받았을 때 
        if len(right):
            move = right.pop()                          # right의 element를 팝하고
            left.append(move)                           # left에 추가해준다
    else:
        if len(left):
            left.pop()                                  # B를 받았을 때 왼쪽 원소 pop
    
print(''.join(left+right[::-1]))

그리고 파이썬의 경우에는 시간초과를 피하기 위해 input()함수를 쓰는 것보다 sys module에서 sys.stdin.readline().strip()을 사용해서 값들을 읽었다. 파이썬 입출력에 대해선 다음에 새로운 포스트로 다뤄보겠다.