📌 개요
알고리즘 문제를 푸는 과정에서, 코드의 간단한 차이가 시간초과 여부를 가르는 현상을 경험했다.
채점 결과, 시간 초과가 발생한 코드
n = int(input())
array = [(i+1) for i in range(n)]
while len(array) > 1:
array.remove(array[0])
array.append(array[0])
array.remove(array[0])
print(array[0])채점 결과, 정답 인정이 된 코드
from collections import deque
n = int(input())
array = deque()
for i in range(n):
array.append(i+1)
while len(array) > 1:
array.popleft()
array.append(array.popleft())
print(array[0])두 코드는 배열을 list로 선언했는지, deque로 선언했는지의 차이가 있는데,
이 차이가 왜 시간 문제를 초래하는지 알아보았다.
📌 list & 시간복잡도
첫번째 코드에서 사용한 list의 주요 메서드는 append, remove이다.
remove를 pop(0)으로 사용하는 방법도 있었을테니, 세가지 방법의 시간복잡도를 알아보았다.
| 메서드 | 시간복잡도 |
| list.append(n) | O(1) |
| list.remove(n) | O(n) |
| list.pop(n) | O(n) |
append(n)의 경우는 O(1)의 시간복잡도를 가지므로 문제와 관련이 없지만,
remove(n)과 pop(n)의 경우, 둘 모두 O(n)의 시간복잡도를 가지므로
문제에서 list의 길이가 최대 500,000이었던 것을 감안하면 문제가 생기는 것이 일리 있다.
📌 deque & 시간복잡도
두번째 코드에서 사용한 deque의 주요 메서드는 append, popleft이며, 그 둘의 시간복잡도를 알아보았다.
| 메서드 | 시간복잡도 |
| deque.append(n) | O(1) |
| deque.popleft() | O(1) |
append(n)과 popleft() 모두 O(1)의 시간복잡도를 가지므로
deque의 길이와는 무관하게 일정한 처리 속도를 가진다는 의미로 볼 수 있을 것이다.
📌 list & deque의 시간복잡도
파이썬 위키에 잘 정리된 시간 복잡도 표가 있어 가져와보았다.
혹시나 다른 메서드를 사용할 일이 있을때 참고하면 좋을 것 같다.
📄 출처 : 파이썬 위키
📌 결론
💡 시간 절약을 위해서는 경우에 따라 list 대신 deque를 사용할 줄 알아야 한다!
