[파이썬] 파이썬 list.pop(0)은 O(n)이다! 그러니 데크(deque)를 쓰자
0. 펠린드롬 문제
펠린드롬 문제를 만나면 보통 list의 0번 인덱스와 마지막 인덱스를 서로 비교해서 같은지 확인하는 방식으로 푸는 것 같다. 나 역시 그 문제를 풀다가 간단하면서도 중요한 개념을 만나게 되었다.
1. list의 pop() 연산
리스트의 pop() 함수는 가장 마지막에 있는 요소를 리턴 후 해당 요소를 삭제한다. 마치 queue처럼 쓸 수 있다. i번째 요소라면 list.pop(i)라고 하여 i번째요소를 찾아서 pop할 수도 있다. 그렇다면 list.pop(0)로 리스트의 0번째 요소를 pop할 수도 있겠다!
2. list.pop(0)의 시간복잡도는 O(n)이다!
리스트의 가장 첫번째 요소를 반환하고 삭제하는 pop(0)는 O(n)의 시간 복잡도를 가진다. 즉 데이터가 크기가 커지면 커질 수록 선형시간에 비례해서 실행 시간이 늘어난다.
파이썬의 list.pop(0)을 쓰면 안 되나요?
백준에서 파이선으로 문제를 몇 개 풀었습니다. 그렇지만 아직 Java나 C만큼 익숙하지 않은 것은 현실입니다. 파이선에는 list.pop(0)이 있는데요. 이것에 대해서 알아보겠습니다. 간단한 테스트 프
codingdog.tistory.com
이 글을 참고하면 pop(0)를 하면 1번 인덱스부터 모두 다 앞으로 하나씩 당겨야하기 때문에 O(n)의 시간이 소요된다는 것! 그렇다면 어떻게 해야할까?
3. deque를 쓰자!
데크(deque) 자료구조는 큐의 선입선출(FIFO) 방식으로 작동되면서 한쪽에서만 push, pop이 일어나던 queue와 달리 양쪽에서 요소를 push, pop 할 수 있다. 파이썬은 이러한 데크 자료구조도 지원한다. 이러한 데크는 push, pop 연산이 자주 일어나는 연산에서 리스트보다 훨씬 우월한 연산 속도를 가지고 있다.