[백준2164_자바스크립트(javascript)] - 카드2

🔴 문제

카드2

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const n = Number(fs.readFileSync(path));

const cards = Array.from({ length: n }, (_, i) => i + 1);

let front = 0;
let cnt = 0;

while (cnt !== n - 1) {
  cards[front++] = 0;
  cnt += 1;
  cards.push(cards[front]);
  cards[front++] = 0;
}

console.log(cards[cards.length - 1]);

🟢 풀이

⏰ 소요한 시간 : 20분

unshift가 O(n)의 시간복잡도를 가지고 있는데 while문안에서 사용하면 O(n^2) 의 시간복잡도를 가지게 된다.
n의 범위가 500,000이므로 총 250,000,000,000정도의 연산을 하게되고 2초내로 해결할 수 없게 된다.
그래서 인덱스 값을 증가시키기로 했다.

cnt는 카드를 몇개 버렸는지 세어주는 변수이름이고 front는 현재 몇번째 인덱스에서 작업중인지를 나타내는 변수이다.
마지막 하나의 카드가 남았을때 결과를 출력해야 하므로 cnt가 n-1이 아닐때만 while문이 동작하도록 한다 조금 더 정확하게는 cnt < n-1 이다.
첫 번째 요소 front의 카드를 버리기 위해 해당 인덱스 위치를 0으로 만들어준다. 하나를 버렸으니 cnt변수를 1 증가시켜 준다. 그 후 첫 번째 요소 front 인덱스의 값을 cards배열의 맨뒤에 삽입하고 해당 인덱스의 값을 0으로 바꿔준다.
마지막 결과 값을 출력해주면 끝

🔵 Ref