벡준

백준 18258 파이썬 풀이 (큐 2, deque)

이전에 비슷한 문제를 풀어본 적이 있다. 저번에는 list를 활용해서 스택을 구현했었다. 이번에도 마친가지로 list를 활용해서 큐를 구현했다. 그러나 문제는 시간초과가 났다. 찾아보니 list로 자료구조를 사용하는 것은 성능측면에서 비효율적이라고 한다. 그 이유는 list는 무작위 접근에 최적화된 구조이기 때문에 pop(0)이나 insert(0,x) 같은 경우는 상당히 불리한 연산이다. 이 두 연산의 시간 복잡도가 n이기 때문에 담고 있는 데이터가 많으면 많을수록 느려지게 된다. 따라서 list가 아닌 다른 형태로 자료구조를 만드는게 좋다고 한다. 그래서 deque를 사용해서 큐를 사용해 보았다. from collections import deque q = deque() q.append(1) # q =..