카드1

문제

언어

  • JavaScript

순서도

  1. 큐 구현
  2. 문제에서 나온 동작을 따라하며, 버린 카드 순서대로 모으기
  3. 버린 카드와 마지막에 남은 카드 출력

문제 풀이 step 1

  • N 장의 카드가 있습니다. 각각의 카드는 차례로 1 부터 N 까지의 번호가 붙어 있으며, 1 번 카드가 제일 위에, N 번 카드가 제일 아래인 상태로 순서대로 카드가 놓여있습니다.
  • 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 됩니다.
  • 우선, 제일 위에 있는 카드를 바닥에 버립니다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮깁니다.
  • 예를 들어, N = 4 인 경우를 생각해보면, 카드는 제일 위에서부터 1 2 3 4 의 순서로 놓여있습니다.
  • 1 버리면 2 3 4 가 남습니다. 여기서 2 를 제일 아래로 옮기면 3 4 2 가 됩니다.
  • 3 을 버리면 4 2 가 되고, 4 를 밑으로 옮기면 2 4 가 됩니다.
  • 마지막으로 2 를 버리고 나면, 버린 카드들은 순서대로 1 3 2 가 되고, 남는 카드는 4 가 됩니다.
  • N 이 주어졌을 때, 버린 카드들을 순서대로 출력하고, 마지막에 남게 되는 카드를 출력하는 문제입니다.

문제 풀이 step 2

  • 우선, 배열을 이용해서 간단한 큐를 만듭니다. 그냥 배열을 사용해도 무방합니다.
  • 1 ~ N 까지의 숫자를 차례대로 큐에 넣어줍니다.
  • 큐가 빌 때까지 아래의 과정을 반복합니다.
    • 큐에서 숫자를 하나 제거하고, 출력을 위해 따로 저장합니다.
    • 큐에서 숫자를 하나 제거하고, 다시 큐에 넣어줍니다.
  • 위 과정을 모두 마쳤으면, 출력을 위해 따로 저장해놓은 것을 출력 형식에 맞게 변환한 다음 출력하면 정답입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

소스 코드

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

// 간단한 큐 구현
class Queue {
	constructor() {
		this.bucket = [];
		this.front = -1;
		this.rear = -1;
	}

	enqueue(item) {
		this.bucket[++this.rear] = item;
	}

	dequeue() {
		return this.bucket[++this.front];
	}

	isEmpty() {
		return this.front === this.rear;
	}
}

const solution = (input) => {
	const n = Number(input[0]);

	// 1 ~ N 까지의 숫자를 차례대로 큐에 넣기
	const queue = new Queue();
	for (let i = 1; i < n + 1; i++) {
		queue.enqueue(i);
	}

	// 문제에서 나온 동작을 따라하며 버린 카드 모으기
	let res = [];
	while (!queue.isEmpty()) {
		res.push(queue.dequeue());
		queue.enqueue(queue.dequeue());
	}

	return res.join(" ");
};

console.log(solution(input));