백준 1406번 파이썬

1406번: 에디터

처음에 떠올린 문제풀이 방법은 

list를 이용해서 insert 나 del 함수를 이용하는 것이었다. 하지만 이 문제는 시간제한이 0.3초로 짧았고, 시간 초과가 났다.

아무래도 최대 명령어 개수가 50만이고, insert만한다면? 파이썬 list 에서 insert의 시간 복잡도는 O(N)이므로, 또한 여기서 최대 문자열 길이는 60만이므로, 50만 * 60만 => 3천만 연산 + 다수의 if문  존재..

시간 초과가 나기 쉽다.

이쯤되면 pop이나 append와 같이 O(1)만큼 시간이 걸리는 연산만 사용해서 문제를 풀 수 있지 않을까? 생각할 수 있다.

stack 자료구조를 2 개 사용해서 문제를 풀 수 있다.

stack 2개를 이용한 문제풀이 그림

코드 

import sys
if __name__ == "__main__":
    stackLeft = list(sys.stdin.readline().rstrip())
    stackRight = list()

    m = int(sys.stdin.readline().rstrip())
    for _ in range(m):
        command = list(sys.stdin.readline().rstrip().split())
        if command[0] == "P":
            stackLeft.append(command[1])

        elif command[0] == "B" and stackLeft:
            stackLeft.pop()

        elif command[0] == "D" and stackRight:
            stackLeft.append(stackRight.pop())

        elif command[0] == "L" and stackLeft:
            stackRight.append(stackLeft.pop())


    print(''.join(stackLeft) + ''.join(list(reversed(stackRight))))

 

참고자료

[python] 백준 1406 런타임 에러, 시간 초과 해결