문제

https://www.acmicpc.net/problem/2164

첫 시도, 시간초과⏰

const solution = length => {
  let queue = Array.from({length}, (_, i) => i+1);
  
  while(queue.length > 1){
    queue.shift()
    queue.push(queue.shift())  
  }
  
  return queue[0]
}

카드 더미를 queue 라고 할 때
Array.from({length}, (_, i) => i+1)로 길이가 length이며 1을 기준으로 i씩 증가하는 값을 가진 배열을 생성했다.

제일 위의 카드는 shift로 제거하고 그다음 위의 카드는 shift로 빼서 push로 카드 더미 제일 밑에 넣는 방식으로 구현했는데 시간 초과 이슈가 있었다.

왜일까? 구글링을 통해 shift / unshift 메소드는 앞쪽의 추가/삭제 시 전체 인덱스가 바뀌므로 시간 복잡도 O(N)이라는 것을 알게 되었다.

참고자료

• 링크드리스트를 통한 구현 https://www.jongung.com/275
• js 배열 메소드의 시간복잡도 https://parkparkpark.tistory.com/m/101

solution

const fs = require('fs');
const input = fs.readFileSync("/dev/stdin").toString().trim()

const solution = length => {
  let queue = Array.from({length}, (_, i) => i+1);
  let s = 0
  while(s !== queue.length-1){
    s++
    queue.push(queue[s])
    s++
  }
  
  return queue[queue.length-1]
}

console.log(solution(input))

카드 더미 제일 위의 카드를 제거해야 한다면 shift를 사용하지 않고 현재 위치에 대한 인덱스s값을 증가시켜 건너뛰는 방식으로 문제를 해결했다.
push / pop 은 시간 복잡도 O(1) 이므로 그대로 사용했다.