팰린드롬 문제

• 팰린드롬(Palindrome): 앞뒤를 뒤집어도 똑같은 문자열
• 팰린드롬 문제를 만나면 보통은 list의 0번 인덱스와 마지막 인덱스를 서로 비교해서 같은지 확인하는 방식으로 푸는데 이때 한 가지 생각해봐야 할 부분이 있음

list.pop(0)의 시간복잡도는 O(n)

• list의 pop() 연산
  • 리스트의 pop() 함수는 가장 마지막에 있는 요소를 리턴 후 해당 요소를 삭제해 마치 queue처럼 쓸 수 있음
    • i번째 요소라면 list.pop(i)라고 하여 i번째요소를 찾아서 pop
    • list.pop(0) → 리스트의 0번째 요소를 pop
• 하지만 리스트의 가장 첫번 째 요소를 반환하고 삭제하는 pop(0)는 O(n)의 시간 복잡도를 가짐
• 즉 데이터의 크기가 커지면 커질수록 선형 시간에 비례해 실행 시간이 증가

pop(0)를 하면 1번 인덱스부터 모두 다 앞으로 하나씩 당겨야하기 때문에 O(n)의 시간이 소요된다.

데크(deque) 자료구조: from collections

• 큐의 선입선출(FIFO) 방식으로 작동
• 한쪽에서만 push, pop이 일어나던 queue와 달리 양쪽에서 요소를 push, pop 할 수 있음
• 데크는 push, pop 연산이 자주 일어나는 연산에서 리스트보다 훨씬 우월한 연산 속도를 가짐 → 파이썬은 데크 자료구조도 지원하므로 해당

참고: 파이썬의 list.pop(0)을 쓰면 안 되나요?