요세푸스 문제(백준 코딩테스트 1158번, Queue, NodeJS 풀이)

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

 

 

문제 수준:

실버4

 

문제 요약:

주어진 N명의 사람이 순서대로 둘러앉아 있다. 이 중 K번 째 사람을 순서대로 뺄 때, 뺀 순서를 구하시오.

7명의 사람이 있고 3을 카운트하며 한 명 씩 뺀다고 할 때,

<3, 6, 2, 7, 5, 1, 4> 순서로 빠지게 된다.

 

입출력 예 (입력 / 출력):

입력 첫 째 줄에는 N명과 기준 K가 주어진다.

 

 

 

문제 풀이 전략:

queue 문제를 많이 안 풀어봐서 이게 queue문제인지 아닌지 많이 헤맸다.

처음 도전하다가 실패한 로직은 아래와 같다.

처음엔 while문 순회로 계속 방문하며

1. 방문한 노드는 넘어가고
2. 방문 안 했으면서 + 주어진 순서가 아니면 순서만 ++하고 넘어가고
3. 방문 안 했으면서 + 주어진 순서면 정답 배열에 넣기

순회 마치면 정답 배열 표출

벌써 방문처리 여부, K번째인지 아닌지, 2가지 조건으로 판별해야되는데 '마지막으로 k번째였던 곳의 위치'에서부터 'K번째인 곳'을 카운트해줘야하고 이게 최대 인원인 N명을 넘어가면 바꿔줘야되는 복잡한 문제가 되어버렸다.

 

그러나 이걸 Queue로 간단히 풀수 있는 문제라는걸 깨닿고는 이마를 탁 쳤다. 

1. 방문처리같은 로직은 버리고, 그냥 K번째가 아니면 queue에서 빼서 뒤로 넣으면 되는 것이었다.

2. K번째인 녀석은 다시 넣지 않고 정답 배열에 넣으면 된다.

 

 

 

내 풀이:

// 메모리 초과 코드
let fs = require("fs");
let [total, interval] = fs.readFileSync("input.txt").toString().split(" ").map(Number);

class Queue { // 내장 queue가 없으므로 queue를 선언. 배열로 shift메소드 사용하면 재정렬 시간이 오래 걸릴 것을 의식해서 queue를 만들었다.
  constructor() {
    this.list = {};
    this.head = 0;
    this.tail = 0;
  }
  enqueue(item) {
    this.list[this.tail] = item;
    this.tail++;
  }
  dequeue() {
    const temp = this.list[this.head];
    delete this.list[this.head];
    this.head++;
    return temp;
  }
  getLength() {
    return this.tail - this.head;
  }
}

let cnt = 0;
const ans = [];
const queue = new Queue();
for (let i = 1; i <= total; i++) {
  queue.enqueue(i); // queue에 일단 다 넣기
}

while (queue.getLength() !== 0) { // queue가 다 빌때까지 반복
  cnt++; // K번째 수를 판별하는 변수
  let deq = queue.dequeue(); //queue에서 하나 뺀다.
  if (cnt === interval) { // k번째 수에 도달하면
    cnt = 0; // cnt를 초기화 시키고
    ans.push(deq); // 정답 배열에 뺀걸 넣는다.
    continue; // queue에는 다시 넣지 않고 continue
  }
  queue.enqueue(deq); // k번째 수가 아니라면 그냥 뒤에 다시 넣는다.
}
console.log("<" + ans.join(", ") + ">"); // 표출.

// 정답은 나오는데 메모리 초과가 떴다...
// class를 선언하는 것이 메모리를 많이 잡아먹나?
// 그래서 그냥 shift를 사용하는 로직으로 바꿔봤다.



// 정답 판정
let fs = require("fs");
let [total, interval] = fs.readFileSync("input.txt").toString().split(" ").map(Number);

let cnt = 0;
const ans = [];
const queue = [];
for (let i = 1; i <= total; i++) {
  queue.push(i);
}

while (queue.length !== 0) {
  cnt++;
  let deq = queue.shift();
  if (cnt === interval) {
    cnt = 0;
    ans.push(deq);
    continue;
  }
  queue.push(deq);
}
console.log("<" + ans.join(", ") + ">");
//shift가 성능이 안 좋다고 들었는데, 이정도 시간적 여유는 주는 문제였나보다.
//자바스크립트로 queue문제 푸는것은 확실히 조금 힘들다.