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

python 으로 백준 1406번 문제를 풀었으나 런타임 오류가 났다. (list의 insert와 pop기능을 통해 처음에 구현했었다.) 테스트 케이스가 잘 돌아가 오류를 못찾겠던 도중 아래의 글을 발견했다.

 

https://www.acmicpc.net/board/view/54572

 

python의 list라는 자료구조의 특성상 시간복잡도가 O(n)이 걸린다고 한다.

insert와 pop부분에서 많은 시간이 걸려 시간초과가 남을 알 수 있었다.

 

본 문제를 풀기 위해서는

1) list 의 맨 뒤에서만 삽입/삭제 연산을 할 수 있도록 알고리즘을 구현하기

2) 한가운데의 원소를 삽입하거나 삭제했을 때 바로 앞뒤의 원소 이외의 원소를 건드릴 필요가 없는 자료구조를 사용하기

둘 중 한가지 방법을 선택해야 하는 것이 좋다는 것을 알게 되었다.

 

1번의 방법으로 해결하려고 했으나 코드가 너무 길어지고 복잡해질 것 같았다.

2번의 방법으로 해결하기 위해서 어떻게 해야할 지 고민하던 도중 stack 2개를 활용해서 풀 수 있음을 알게 되었다.

 

import sys

if __name__ == '__main__':
    stackLeft = list(sys.stdin.readline().rstrip())
    stackRight = list()
    
    n = int(sys.stdin.readline().rstrip())
    for i in range(0, n):
        command = list(sys.stdin.readline().split())
        if command[0] == 'L' and stackLeft:
            stackRight.append(stackLeft.pop())
        elif command[0] == 'D' and stackRight:
            stackLeft.append(stackRight.pop())
        elif command[0] == 'B' and stackLeft:
            stackLeft.pop()
        elif command[0] == 'P':
            stackLeft.append(command[1])

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