[백준] 1158 | 요세푸스 문제 | Javascript

문제

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

 

정답 코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";

const input = fs.readFileSync(filePath).toString().trim().split(" ");

function solution(input) {
  const N = Number(input[0]);
  const K = Number(input[1]);

  const result = [];
  const people = [];
  let startIdx = 0;

  for (let i = 1; i <= N; i++) {
    people.push(i);
  }

  while (people.length) {
    let removeIndex = (startIdx + (K - 1)) % people.length;

    // 해당 인덱스의 요소를 배열에서 제거
    result.push(people[removeIndex]);
    people.splice(removeIndex, 1);

    startIdx = removeIndex % people.length;
  }

  return `<${result.join(", ")}>`;
}

console.log(solution(input));

배열에서 제거할 요소의 인덱스를 계산하는 방식으로 풀었다. 배열의 크기가 줄어들기 때문에, 긱 반복마다 남은 배열의 크기에 따라 인덱스를 갱신해야한다. 

• startIndex :  현재 배열에서 K 번째 인덱스를 찾기 위한 시작 위치. 제거된 요소 이후, 다음 요소에서 시작.
  • 해당 문제가 순환 배열이므로, 끝에서 넘어가면 다시 처음으로 돌아간다. 이를 수학적으로 처리하기 위해 모듈러 연산을 사용한다.
  • 주어진 배열에서 특정 요소를 제거한 뒤, 그 다음 인덱스를 가리키는 계산을 하려면 현재 인덱스를 기반으로 남은 배열의 범위 안에서 올바른 인덱스를 갱신해야한다. 해당 식은 다음과 같다. 다음 인덱스=(현재 인덱스%현재 배열 길이)
• removeIndex : 현재 배열에서 K 번째 인덱스를 나타내며, 제거 대상의 위치.
  • removeIndex 를 구하는 식은 index=(현재 인덱스+(K−1))%현재 배열 길이 이다.
  • 현재 인덱스 : 이전에 제거된 요소 바로 다음에서 시작하는 인덱스를 의미한다. 초기값은 0 이다.
  • K : 제거하고 싶은 간격
  • 현재 배열 길이 : 반복마다 배열에서 요소가 제거되므로, 이 값은 동적으로 변해야한다.

 

다른 분들은 큐를 활용하여 풀었는데... 나는 좀 비효율적으로 푼 듯하다..