[알고리즘/백준/2164] 카드2(자료구조, 큐)

문제

---

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

2164번: 카드2

 

풀이

---

class Queue {
  constructor() {
    this.data = [];
    this.head = 0;
    this.tail = 0;
  }
  push(item) {
    this.data[this.tail++] = item;
  }
  pop() {
    this.head++;
  }
  front() {
    return this.data[this.head];
  }
  rear() {
    return this.data[this.tail - 1];
  }
  isEmpty() {
    return this.head === this.tail;
  }
  size() {
    return Math.abs(this.head - this.tail);
  }
}

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let N = +fs.readFileSync(filePath).toString().trim();

const q = new Queue();
for (let i = 0; i < N; i++) {
  q.push(i + 1);
}

while (q.size() > 1) {
  q.pop();
  q.push(q.front());
  q.pop();
}

console.log(q.front());

카드에서 가장 위에 있는 카드를 버리고, 그 다음으로 제일 위에 있는 카드를 가장 아래로 옮긴다. 이것을 카드가 1장 남을 때까지 반복했을 때 남는 카드를 구하는 문제이다. 

 

큐에 카드를 1~N까지 넣고 1개가 남을 때까지 위에서 하나를 빼고, 그 다음 카드를 마지막으로 옮겨주는 작업을 반복한다. 

그리고 마지막 남은 카드를 출력한다. 

이때 pop은 head의 값을 증가시키는데, front는 가장 첫 번째 값을 읽는 메서드이다.