관련 문제
https://school.programmers.co.kr/learn/courses/30/lessons/118667
😥Problem: 시간초과
시행착오
처음에는 단순 for문의 반복 횟수의 문제라고 생각했다. 왜나면 pop(0)과 같은 연산이 모두 시간복잡도가 O(n)일거라 생각했기 때문이다.
Why?
- 기존코드는 list로서 queue를 list.pop(0) 하고 append 하는 방식으로 진행하였다.
- list로 pop(0)을 하면 시간복잡도가 O(1)일거라고 생각했다.
- 그러나 마지막 원소 삭제는 O(1)이 맞지만 맨 앞 원소 삭제는 아래 그림처럼 앞으로 원소들이 당겨지기 때문에 O(n)이다.
사진출처
😊Solution: deque 사용
from collections import deque위 라이브러리를 이용해서 파라미터로 들어온 리스트를 deque로 바꿔주고 pop(0)대신에 popleft() 함수로 pop해주었다.
추가 함수들
deque.append(a) : 맨 오른쪽(뒷쪽)에 원소 추가
deque.appendleft(a): 맨 왼쪽(앞쪽)에 원소 추가
deque.pop() : 맨 오른쪽(뒷쪽) 원소 pop
deque.popleft() : 맨 왼쪽(앞쪽) 원소 pop
-> 모두 시간복잡도 O(1)
ML_engineer