[Python] 1406 에디터

알고리즘 분류에 최근 공부한 자료구조, 스택, 연결 리스트가 있어 풀게 된 문제이다.

첫 시도에서는 비슷한 문제를 풀어봤던 경험을 살려 인덱스를 커서로 이용한 풀이를 시도해보았다. L, D, F는 인덱스를 움직이는 것으로 해결하였다. P의 경우에는 커서를 기준으로 리스트를 두 개로 슬라이싱한 뒤 앞의 리스트에 입력받은 문자를 새로 추가하는 방식을 이용했다.

그러나 0.3초의 시간 제한은 제법 빠듯했고, 인터넷을 참고하여 소요 시간을 줄일 수 있는 다른 방법을 찾아 풀었다.

import sys

prelst = list(sys.stdin.readline().strip())
postlst = []
n = int(sys.stdin.readline())

for i in range(n):
    command = sys.stdin.readline().split()

    if command[0] == 'L':   # 커서를 왼쪽으로 한 칸 옮김
        if prelst:
            postlst.append(prelst.pop())

    elif command[0] == 'D':     # 커서를 오른쪽으로 한 칸 옮김
        if postlst:
            prelst.append(postlst.pop())

    elif command[0] == 'B':     # 커서 왼쪽에 있는 문자를 삭제함
        if prelst:
            prelst.pop()

    elif command[0] == 'P':     # 문자를 커서 왼쪽에 추가함
        prelst.append(command[1])

print(''.join(prelst) + ''.join(reversed(postlst)))

시작부터 스택을 두 개로 나누었고, 커서를 옮기고 문자를 삭제/추가하는 과정은 인덱스 대신 append와 pop을 활용하였다.

Big-O 표기법을 이용해 시간 복잡도를 확인해 보았다.
인덱스를 이용하여 문자를 제거할 경우 시간복잡도가 O(N)이다. 그러나 인덱스를 지정하지 않고 pop으로 문자를 제거하면 시간복잡도는 O(1)으로 감소한다.

인덱스를 이용하지 않고, 문자를 두 스택 사이에서 옮기고 제거하는 것만으로 시간 복잡도를 줄일 수 있었다. 아직은 자료구조의 기초 단계를 배우는 중이기에 큰 차이를 느끼지 못할 수 있지만 추후 복잡한 알고리즘을 다루게 되면 코드 한 줄에 따라 실행 시간에 큰 변화가 생길 수도 있을 것이다. 단순히 문제를 맞추는 것에 급급하지 말고, 이 코드 한 줄이 전체 프로그램에 어떤 영향을 미칠지 생각하며 멀리 내다보는 코딩 습관을 가져야겠다고 느꼈다.