[백준] Javascript의 shift() 사용했을때 시간초과

관계 리스트를 만들때 input에서 shift()를 해서 받아와 만들었는데

시간초과가 났다.. 

// 연결 관계리스트 만들기
for (let i = 0; i < M; i++) {
  let [x, y] = input.shift().split(" ").map(Number);
  graph[x].push(y);
  graph[y].push(x);
}

 

검색해보니 shift()가 많이 느리다고하네 .. 

배열의 끝이 아닌 임의의 위치에서 항목을 삭제하는 것은 큰 대가를 치뤄야 하기 때문입니다. 

그래서 index를 지정해서 설정해줬다.

// 연결 관계리스트 만들기
for (let i = 0; i < M; i++) {
  let [x, y] = input[i].split(" ").map(Number);
  graph[x].push(y);
  graph[y].push(x);
}

 

https://www.acmicpc.net/board/view/47602

글 읽기 - Node.js 11724번 BFS 시간초과

 

궁금해서 더 검색해보니

shift() 는 최악의 경우 시간복잡도가 O(N)이다.

 

shift is at worst O(N) however it can, in specially cases, be implemented as O(1) at the cost of slowing down indexing so your mileage may vary.

 

https://stackoverflow.com/questions/22614237/javascript-runtime-complexity-of-array-functions

JavaScript runtime complexity of Array functions

 

shift 나 unshift 는 배열 맨 앞에 넣거나 빼면서 남은 배열의 index가 모두 바뀌기 때문이다. 

시간초과가 난다면 shift , unshift를 쓴 곳을 잘 봐야겠다.