[인프런] Node.js / 섹션6-자료구조(큐) / 6. 공주 구하기

문제

다음과 같은 방법으로 공주를 구하러 갈 왕자를 결정한다.

1번 왕자부터 N 번 왕자까지 순서대로 시계 방향으로 돌아가며 동그랗게 앉게 한다. 그리고 1번 왕자부터 시 계방향으로 돌아가며 1부터 시작하여 번호를 외치게 한다. 한 왕자가 K(특정숫자)를 외치면 그 왕자는 공주를 구하러 가는데서 제외되고 원 밖으로 나오게 된다. 그리고 다음 왕자부터 다시 1부터 시작하여 번호를 외친다. 이렇게 해서 마지막까지 남은 왕자가 공주를 구하러 갈 수 있다.

예를 들어 총 8명의 왕자가 있고, 3을 외친 왕자가 제외된다고 하자. 처음에는 3번 왕자가 3 을 외쳐 제외된다. 이어 6, 1, 5, 2, 8, 4번 왕자가 차례대로 제외되고 마지막까지 남게 된 7 번 왕자에게 공주를 구하러갑니다.

N과 K가 주어질 때 공주를 구하러 갈 왕자의 번호를 출력해보자.

 

풀이

function solution(n, k) {
  let answer;
  const queue = Array.from({ length: n }, (v, i) => i + 1); // js는 항상 첫번째 인자는 value 두번째는 index
  while (queue.length) {
    for (let i = 1; i < k; i++) queue.push(queue.shift());
    queue.shift(); // k번 외친 사람 - 그냥 제거
    if (queue.length === 1) answer = queue.shift();
  }
  return answer;
}

console.log(solution(8, 3));

먼저 큐 라는 배열을 만든다. 이는 1부터 왕자 수까지의 수로 이루어져있다.(왕자 자리 매김)

왕자가 차례대로 숫자를 부를때, 숫자를 부른 왕자는 빠지고(shift) 다시 맨 뒤로 들어간다(push).

그러다가 해당 숫자를 부른 왕자는 그냥 빠지기만 한다(shift)

이 과정을 반복하다가, 한명만 남으면 그 왕자가 정답이다.