[백준/JS] 1185 요세푸스 문제

문제링크

1158번: 요세푸스 문제

 

문제사항

요세푸스문제 클래스 큐를 구현해서 풀고 있는데 , 메모리초과가 계속 나네요. 그런데 이유를 정말 모르겠습니다.

로직은 환형큐를 사용해서 K번째가 아닌 수는 큐에 다시 넣어주는 방식으로 구현했습니다.

N이 7이고 K가 3일때 
[1, 2, 3, 4, 5, 6, 7] -> [3, 4, 5, 6, 7, 1, 2] => 3 삭제
[4, 5, 6, 7, 1, 2] -> [6, 7, 1, 2, 4, 5] => 6 삭제
[7, 1, 2, 4, 5] -> [2, 4, 5, 7, 1] => 2 삭제
[4, 5, 7, 1] -> [7, 1, 4, 5] => 7 삭제
[1, 4, 5] -> [5, 1, 4] => 5 삭제
[1, 4] -> [1, 4] => 1 삭제
[4] => 4 삭제

 

오답

class Queue {
  constructor() {
    this.elements = {};
    this.head = 0;
    this.tail = 0;
  }
  enqueue(element) {
    this.elements[this.tail] = element;
    this.tail++;
  }
  dequeue() {
    const item = this.elements[this.head];
    delete this.elements[this.head];
    this.head++;
    return item;
  }
  peek() {
    return this.elements[this.head];
  }

  back() {
    return this.elements[this.tail - 1];
  }
  get length() {
    return this.tail - this.head;
  }
  get isEmpty() {
    return this.length === 0;
  }
}

const fs = require("fs");

BOJkey = 0;

var input = fs
  .readFileSync(BOJkey ? "./자바스크립트로/1158/input.txt" : "./dev/stdin")
  .toString()
  .trim()
  .split(" ");

let result = [];
let q = new Queue();
for (let i = 1; i <= input[0]; i++) {
  q.enqueue(i);
}
let count = 0;
while (!q.isEmpty) {
  count++;
  if (count == input[1]) {
    count = 0;
    result.push(q.dequeue());
  } else {
    q.enqueue(q.dequeue());
  }
}
let ans = "<";
result.map((el) => (ans += String(el) + ", "));
ans = ans.slice(0, -2);
console.log(ans + ">");

 

참고한 풀이

링크드리스트 형태로 푸셨다. 진짜 대단하신 것 같다.

const [num, skip] = require('fs').readFileSync('/dev/stdin').toString().trim().split(' ').map((x) => parseInt(x));
let board = [];
let printer = '<';
let pointer = 0;

for (let i = 0; i <= num - 1; i++)
    board.push({ 'current': i, 'next': i + 1 });
board.push({ 'current': num, 'next': 1 });

for (let i = 1; i <= num; i++) {
    for (let j = 1; j <= skip - 1; j++)
        pointer = board[pointer].next;

    let previous = pointer;
    pointer = board[previous].next;
    let next = board[pointer].next;

    printer += pointer + ', ';
    board[previous].next = next;
}

printer = printer.slice(0, -2) + '>';
console.log(printer);