[백준/JS] 1158번_요세푸스 문제

 

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

1158번: 요세푸스 문제

 

---

[ 문제 설명 ]

 

예제에서 N = 7, K = 3으로 주어졌으므로 1,2,3,4,5,6,7 이렇게 있다면 먼저 3번째 수인 3을 꺼내기 위해서는

앞의 1,2를 꺼낸 후 3을 꺼내서 제거해야한다. 꺼낸 1,2는 7뒤에 붙어서 3을 꺼낸 후 형태는 4,5,6,7,1,2 가 되므로 다음

꺼낼 세번째 수로는 6이 되고 이 과정이 모든 수가 제거될 때까지 반복된다. 

 

[ 문제 풀이 ]

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(e=>e.replace("\r",""));
const [n,k] = input[0].split(' ');

const queue = [];
const answer = [];

for (let i = 0; i < n; i++){
    queue.push(i+1);
}

let count = 1;
// 배열의 길이 0이 될 때까지 while문 통해 큐에서 맨 앞자리 하나빼줌(shift 이용)
while (queue.length) {
    const shiftItem = queue.shift();
    // 만약 k번째라면 answer에 push
    if (count % k === 0) {
        answer.push(shiftItem); // 3
    // 아니면 큐에 다시 push
    }else {
        queue.push(shiftItem); // 1,2
    }
    count += 1;
}

console.log(`<${answer.join(', ')}>`);