[백준 2164번] 카드 2 - JavaScript

 

이 문제는 읽어보면 동작 방식이 큐(queue)를 사용해야한다는 생각이 들 것이다.

나는 아직 코딩 테스트 초보라 생각이 들지 않았기 때문에 무식하게 먼저 풀어보았다.

 

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

const num = +input;
const queue = Array.from({ length: num }, (_, i) => i + 1);

let front = 0;

for (let i = 1; i <= num; i++) {
	cards.push(i);
}

while (cards.length > 1) {
	cards.shift();
	let n = cards.shift();
	cards.push(n);
}

console.log(+cards);

 

 

언제나 그렇듯 무식하게 풀면 시간 초과 에러가 발생한다. GPT에게 물어보니 .shift()를 수행하는 시간 복잡도가 O(N)이라고 한다.

 

그래서 큐(queue)를 사용하는 방식으로 바꾸어 풀어보았다.

 

소스 코드

const input = require('fs')
	.readFileSync('./info.txt')
	.toString()
	.trim()
	.split('\n');

const num = +input;
const queue = Array.from({ length: num }, (_, i) => i + 1);

let front = 0;

while (queue.length - front > 1) {
	front++;
	queue.push(queue[front]);
	front++;
}

console.log(queue[front]);

 

정답!