[자료구조] JavaScript에서 배열의 pop 과 shift

 

 

JavaScript에서 배열의 pop 과 shift 는 스택/큐 구현을 쉽게 해준다. 

 

코딩테스트 연습을 하다보니 자꾸 시간 초과가 나서 왜 때문인가 찾아봤더니만, pop 메서드는 시간 복잡도 O(1) 을 가지는 반면, shift 메서드는 시간 복잡도 O(n) 을 가진다.  

 

pop

pop 메서드는 배열의 마지막 요소를 제거하고 그 요소를 반환한다. 

const arr = [1, 2, 3, 4, 5];
const lastElement = arr.pop();  // lastElement는 5, arr는 [1, 2, 3, 4]

 

시간 복잡도는 O(1) 으로, 배열의 마지막 요소에 접근하고 이를 제거하는 작업이므로, 배열의 길이에 관계없이 일정한 시간이 걸린다. 

 

shift 

shift 메서드는 배열의 첫번째 요소를 제거하고 그 요소를 반환한다. 

const arr = [1, 2, 3, 4, 5];
const firstElement = arr.shift();  // firstElement는 1, arr는 [2, 3, 4, 5]

 

시간 복잡도는 O(n) 으로, 첫번째 요소를 제거한 후 나머지 모든 요소를 한 칸씩 앞으로 이동시켜야 하므로, 배열의 길이에 비례하여 시간이 걸린다.

 

---

 

 

따라서, 혹시라도 shift 메서드를 사용하는데 시간 초과 오류가 발생한다면 배열을 reverse 해준 후 pop 메서드를 사용해보자!

const arr = [1, 2, 3, 4, 5]; 

const element = arr
               .reverse() // [5, 4, 3, 2, 1]
               .pop(); // return 1