[BOJ - Silver 5] 11866 요세푸스 문제 0

❓문제 설명

• 구현문제
  
• 순열을 구하는 문제로 N명이 원을 이루고 있을 때 K번째 순서를 계속해서 제거해 나가는 방식이다.
• 최종적으로 <제거된 순서>를 구하면 된다

✅ 문제 해결

• 배열에서 특정 K의 배수에 해당하는 인원을 제거하고 그 이후로 다시 K를 세면서 계속 제거를 하는 방식이 필요했다.
• 처음에 계속 문제를 풀려고 했는데 제대로 구현이 안되서 참고를 하여 구현을 하게 되었다.

const fs = require("fs");
const [n, k] = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split(" ")
  .map(Number);

const solution = (n, k) => {
  const people = Array.from({ length: n }, (_, index) => index + 1);
  let count = 0;
  let i = count - 1;
  const result = [];
  while (result.length !== n) {
    i++;
    count++;
    if (count % k === 0) {
      const [number] = people.splice(i, 1);
      result.push(number);
      i--;
    }
    if (i === people.length - 1) {
      i = -1;
    }
  }

  return `<${result.join(", ")}>`;
};
console.log(solution(n, k));

• 중요한 것은 카운트는 계속해서 올라가면서 배수에 해당하는 순간에 계산을 하는데 이때 index를 초기화를 언제할 것인지가 중요하다고 생각이 되었다.
• 결과적으로는 요세푸스 순열에 대해서 어떻게 풀어야할지 알 수 있었다.

🔥 인상 깊은 남의 풀이

const fs = require('fs');
const [n, k] = fs.readFileSync("/dev/stdin").toString().trim().split(' ').map(Number)

const solution = (n, k) => {
  let arr = new Array(n).fill(0)
  arr.forEach((el, i) => arr[i] = (arr[i-1] || 0) + 1)
    
  let i = -1
  let count = 0
  let result = []
  
  while(result.length !== n){
    i++
    count++
    if(count % k === 0){
      result.push(arr[i])   
      arr.splice(i,1)
      i--
    }
    if(i === arr.length-1){
      i = -1
    }
  }
  return '<' + result.join(', ') + '>'
}

console.log(solution(n, k))

❕느낀점

• Array.from을 통해서 오름차순의 배열을 쉽게 만들 수 있는데 자꾸 깜빡하기에 자주 알고리즘을 풀면서 익혀야겠다.
• 배열에서 특정 index의 값을 제거하고 그 값을 이용할 때에는 splice()가 잘 사용되는 것 같다
• while문을 이용해서 반복문을 수행하는 것에 대해서 좀 더 자주 사용해서 문법과 어떻게 계산이 이루어지는지를 잘 알아야 할 것 같다.