[BOJ]9012 괄호 - python

https://www.acmicpc.net/problem/9012

스택을 이용한 기초적인 문제로 코드는 다음과 같습니다.

import collections
import sys
 
 
def is_vps(x):
    stack = collections.deque()
    for i in x:
        if i == "(":
            stack.append(i)
        else:
            if len(stack) == 0:
                return False
            else:
                stack.pop()
 
    if len(stack) == 0:
        return True
 
    return False
 
 
T = int(input())
 
for _ in range(T):
    ip = sys.stdin.readline().rstrip()
 
    if is_vps(ip):
        print("YES")
    else:
        print("NO")
 
 
 

내장모듈인 collection의 deque를 사용했을때와 list를 사용했을때의 시간이 다르게 나왔는데 위의 문제의 경우 list를 사용했을때 더 짧은 시간으로 해결했습니다.

deque를 사용할때 더욱 빠를것이라 생각했지만 구글링을 통해 검색해보니

https://docs.python.org/ko/3/library/collections.html?highlight=deque#collections.deque

https://stackoverflow.com/questions/23487307/python-deque-vs-list-performance-comparison

https://stackoverflow.com/questions/3917574/how-is-pythons-list-implemented

https://stackoverflow.com/questions/6256983/how-are-deques-in-python-implemented-and-when-are-they-worse-than-lists

위의 글들을 보면 python에서 list의 경우에는 동적 array로 구현되어 있고 deque의 경우 양방향 linked-list의 형태로 구현되었음을 알수있다.

따라서 stack의 동작을 생각해보면 동적 array와 linked-list의 append와 pop 연산은 둘다 O(1)임을 알 수 있다.

list가 더 빠른이유는 생성할때 동적 array의 경우가 더 빠르고, pop과 append 연산시에 같은 시간복잡도 일지라도 linked-list가 자신과 연결된 node의 주소값을 저장하는 과정과 linked-list의 끝을 가리키는 값 수정 등 여러 추가사항이 있어서 조금 더 느린것으로 예상된다.

deque가 list보다 빠른 경우는 위의 글에서 보여주듯이 두 배열의 맨 앞에 추가하는 연산인 deque의 appendleft 와 list의 insert이다.

위의 경우에는 deque의 시간복잡도는 O(1) 이고, list는 동적 array이므로 모든 요소를 왼쪽으로 옮기는 연산 때문에 O(n)의 시간복잡도를 갖는다.

따라서 스택을 활용할때는 list를, 큐를 활용할때는 deque를 사용하는것이 유리할것으로 보인다.