문제

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.

출력

첫째 줄에 남게 되는 카드의 번호를 출력한다.

예제 입력

6

예제 출력

4

내가 했던 풀이 방법

shift와 unshift를 이용해서 풀이 -> 실패 (시간초과) shift가 큐처럼 구현할 수 있지만, 삭제후 배열을 재정렬을 하기 때문에 시간이 많이 소요된다는 걸 알게되었다.

※ 해당 문제는 Queue를 이용하여 풀이하였으며, Queue 구현은 [자료구조] JS로 구현하는 큐 (Queue)를 참고하여 구현했습니다.

1. class를 이용해 큐를 구현한 뒤, 1부터 N까지를 queue에 담아준다.
2. while문을 돌면서 queue의 size가 1이 될 때까지 삭제-맨 뒤로 이동-삭제-맨 뒤로 이동을 반복해준다.

코드

var fs = require('fs');
let N = fs.readFileSync(0, 'utf-8').toString().trim();
N = Number(N);

class Queue {
  constructor() {
    (this.storage = {}), (this.front = 0), (this.rear = 0);
  }

  size() {
    if (this.storage[this.rear] === undefined) return 0;
    else return this.rear - this.front + 1;
  }

  enqueue(value) {
    if (this.size() === 0) this.storage['0'] = value;
    else {
      this.rear += 1;
      this.storage[this.rear] = value;
    }
  }

  dequeue() {
    let value = this.storage[this.front];
    delete this.storage[this.front];
    if (this.front === this.rear) {
      this.front = 0;
      this.rear = 0;
    } else {
      this.front += 1;
    }
    return value;
  }

  print() {
    for (let key in this.storage) {
      if (key !== undefined) console.log(this.storage[key]);
    }
  }
}

let queue = new Queue();
for (let i = 1; i <= N; i++) {
  queue.enqueue(i);
}

while (true) {
  if (queue.size() === 1) break;
  queue.dequeue();
  if (queue.size() === 1) break;
  queue.enqueue(queue.dequeue());
}

queue.print();

회고

10일 전쯤에 index값을 이용해서 풀이도 해보고 ushift랑 shift를 이용해서 풀이했는데 시간초과 걸려서 자바스크립트로 큐를 구현하는 방법에 대해 공부한 뒤 구현하기 위해서 미뤄두다가 오늘부터 자료구조를 공부하기로 한 김에 큐를 공부하는 문제로 풀이했다. 자바에서는 queue가 자체적으로 구현되어 있어서 사실 이렇게까지 queue의 구조를 생각하는 건 2학년 때 자료구조 때 이후로는 없던 것 같다.. 자바스크립트 공부를 시작하면서 자료구조 공부의 필요성을 좀 더 느끼고 있는 것 같다. 자바스크립트를 기준으로 한 자료구조 책을 찾기가 정말 힘들어서 살짝 걱정이 되지만 그래도 구글선생님이 있으니까 할 수 있을 것..이다