[Nodejs]1158번: 요세푸스 문제

첨에 듣고 뭔소린지...

위키백과에 검색해보니

n명이 동그랗게 모여있을 때 임의의 한 명부터 순서를 세어 k번째 사람을 모임에서 제외한다. 남은 n-1명에서 다시 다음 사람부터 순서를 세서 k번째 사람을 모임에서 제외한다. 

이해했음. 해당 사람을 빼고, 그 다음 index부터 또 k만큼 세서 지우고... 이걸 반복한다는 얘기였다.

 

[1,2,3...n] 으로 이루어진 배열을 만들고, 한 바퀴를 돌기 전 해당하는 k번째 값들을 0으로 바꾼다.

한 바퀴를 돌았다고 인식하면, 0인 값들을 filter로 지우고 반복하는 코드로 짰었다.

문제는.. 후반부에 꼬이는 이유를 도저히 이해못하겠어서 그냥 복잡하게 생각 말고 직관적으로 구현해보자 생각했다. 

말그대로 매번! k만큼 도는 반복문 안에서, 배열값을 하나씩 검사하면서 담고 바로 삭제하고 이런..

  const N = parseInt(inputArray[0]);
  const K = parseInt(inputArray[1]);
  const resultArray = [];
  let index = 0;
  let peopleArray = Array.from(Array(N).keys()).map((x) => x + 1);

  
  for (let i = 0; i < N; i++) {
    // peoplearray의 모든 요소에 대해
    let innerK = 1;
    while (innerK <= K) {
      if (innerK === K) {
        // K번째 요소
        resultArray.push(peopleArray[index]);
        peopleArray.splice(index, 1);
        break;
      }
      index = (index + 1) % peopleArray.length;
      innerK++;
    }
  }
    console.log("<" + resultArray.join(", ") + ">");

맞추긴 했는데... 이번 문제만큼 내가 바보된 기분을 느낀건 첨인듯...

맞춘 퍼센티지는 절반에 가까운걸 보면 비교적 쉬운 문제인데 나는 거의 만 하루를 끙끙댔기 때문에..ㅠㅠ

다음부터는 저 퍼센티지부분을 안보려고.. 

 

그리고 이 문제는 해결방법이 여러갠거같아서 여러 시도를 해볼 예정.

지금 코드도 더 간단하게 표현할 방법이 있을거다.