[백준] 2164번: 카드2 (실버4) - Javascript 풀이

백준에서 자바스크립트를 사용해서 문제를 푸는 방법은 아래 블로그를 참고했다.

https://nyang-in.tistory.com/156

[백준]백준에서 node.js 입출력 방법 정리(백준/자바스크립트/코딩테스트/알고리즘)

 

여기서 내 VSCode는 fs를 불러올 때

A Node.js builtin module should be imported with the node: protocol 오류가 발생했다.

내 VSCode에서 코드 검사 도구(ESLint, Biome 등)를 사용하고 있기 때문이었다. 이 도구들은 빌트인 모듈을 명시적인 node: 프로토콜로 임포트하도록 강제한다. 따라서 아래와 같이 모듈을 불러와야했다.

const fs = require('node:fs');

 

 

문제 링크

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

 

구현 & 풀이

첫 답안은 시간 초과가 났다.

const fs = require('node:fs');
const n = Number.parseInt(fs.readFileSync('예제.txt','utf8')); // 백준 경로:'/dev/stdin'

const stack = [];
for(i=1;i<n+1;i++){
    stack.push(i); //stack = [1,2,3,4]
}

while(stack.length>1){
    stack.shift(); //제일 위에 있는 카드를 버림 234  
    if(stack.length>1){
        const first = stack.shift();
        stack.push(first); //이후 제일 위에 있는 카드를 맨 밑으로 옮김  342
    }
}

console.log(stack[0]);

 

생각해보니 굳이 while문 내에서 동일한 조건의 if문을 사용할 필요가 없어서 코드를 줄였다.

const fs = require('fs');
const n = Number(fs.readFileSync('/dev/stdin', 'utf8'));

const queue = Array.from({ length: n }, (_, i) => i + 1); // 1~N까지 초기화

while (queue.length > 1) {
    queue.shift(); // 첫 번째 카드 버림
    queue.push(queue.shift()); // 그다음 카드를 뒤로 보냄
}

console.log(queue[0]); // 마지막 남은 카드 출력

 

하지만 계속 시간초과가 났는데, 그 이유는 shift() 메서드의 비효율성 때문이다. shift() 연산은 배열의 첫 번째 요소를 제거하고 나머지 모든 요소를 한 칸씩 앞으로 이동시키는 O(n) 시간 복잡도를 가진다. 큰 n 값에 대해 이 연산을 반복적으로 수행하면 전체 시간 복잡도 성능이 크게 저하된다.

 

따라서 실제로 자료구조를 조작하는 것이 아니라 포인터를 조작하는 방법을 사용했다. 

const fs = require('node:fs');
const n = Number.parseInt(fs.readFileSync('예제.txt','utf8')); // 백준 경로:'/dev/stdin'

const deque = []
for(let i=1; i<=n; i++) deque.push(i);

let front = 0; //첫번째 원소를 가리키는 포인터

while(deque.length - front > 1){
    front++; //첫번째 카드 버리기
    deque.push(deque[front]); //두번째 카드를 맨 뒤로 이동
    front++; //세번째 카드가 맨 위에 있음
}

console.log(deque[front]);

 

 

포인터를 통해 인덱스만 조작하므로 O(1) 시간 복잡도를 가져 효율적이다.

 

🚀 Deque(덱) vs 일반 Queue(큐) 비교

자료구조	삽입(push)	삭제(shift/pop)	양 쪽 조작
Queue	O(1)	O(N) (shift)	❌ 한쪽에서만 삽입, 반대쪽에서 삭제
Deque(Double-ended Queue)	O(1)	O(1)	✅ 양쪽 조작 가능

 

=>자바스크립트는 기본적으로 Array를 사용해서 구현한다. 이때 shift()를 사용하지 않고, 포인터를 사용해 Deque처럼 구현하는 것이 효율적이다.