[PS] 백준#1406 / 에디터

알고리즘 문제 풀이

• 링크 : 에디터
• 유형 : 자료구조, 스택
• 해결 : solved

풀이과정

1. 두 개의리스트를 만들고 A에는 입력받은 초기문자열 B에는 빈 스택.
2. 커서를 왼쪽으로 이동하면 A에서 pop한 데이터를 B 스택에 push
3. 커서를 오른쪽으로 이동하면 반대로 동작
4. 삭제와 삽입은 A에서 일어나도록.

놓친 점

• 처음에는 리스트 하나로 두고 커서의 위치를 저장하는 index 변수를 변경해가는 방식으로 처리했더니 시간초과 발생.
• 이유 : 리스트 하나로 처리하다보니 insert를 사용하게 되는데 노드를 하나 삽입시 그 뒤에 모든 노드들이 하나씩 밀려나는 연산이 필요하게 된다.
• 커서 이전/이후로 나누어서 리스트 두개로 저장한 다음 마지막에 스택부분만 거꾸로 조회해서 이어붙이면 된다.

소스코드

import sys
input = sys.stdin.readline
str = list(input().rstrip())
N = len(str)
M = int(input())
commands = [ input().rstrip().split() for _ in range(M)]
index = len(str)

def execute(str, stack, cmd, char=None):

    if cmd == 'L' and str != []:
        stack.append(str.pop())
    if cmd == 'D' and stack != []:
        str.append(stack.pop())
    if cmd == 'B' and str != []:
        str.pop()
    if cmd == 'P':
        str.append(char)

stack = []
for c in commands:
    index = execute(str=str, stack=stack, cmd=c[0], char= c[1] if len(c) ==2 else None)

print(''.join(str+stack[::-1]))