[ch6. 자료구조(스택, 큐)] 공주 구하기 javascript

해당 포스팅은 인프런의 "자바스크립트 알고리즘 문제풀이" 강의 중 챕터6의 공주 구하기 문제 풀이를 다룬다. 큐로 풀이하였다.

문제

풀이

왕자가 n명이 동그랗게 앉은 후, 시계방향으로 1부터 시작해서 번호를 외친다. 한 왕자가 k를 외치면 그 왕자는 제외되고, 그 다음 왕자부터 다시 1부터 시작해서 번호를 외친다.

남은 왕자가 1명일 때까지 반복문을 돌리면서, 배열의 인덱스 0부터 k-1까지의 원소를 뒤로 옮기고, 배열의 앞 원소를 제거하는 작업을 하면 된다.

예를들어 k가 3이라면 배열의 인덱스 0부터 2까지의 원소를 뒤로 옮기고, 배열의 앞 원소를 제거(k를 외친 왕자)한다. 이 작업을 남은 왕자가 한 명 남을 때까지 반복하면 3, 6, 1, 5, 2, 8, 4번 왕자가 차례로 제외되고 배열에는 7만 남게 된다. 이 7이 공주를 구하러 갈 왕자이다.

전체 코드

let n = 8;
let k = 3;
console.log(solution(n,k));

function solution(n, k) {
  	// 왕자 배열 만들기
    const arr = [...Array(n)].map((_, i) => i+1);
    // 왕자가 한 명만 남을 때까지
  	while (arr.length > 1) {
      	// 배열의 0부터 k-1까지 원소들을 배열의 뒤로 옮기기
        const sp = arr.splice(0, k-1);
        arr.push(...sp);
      	// k를 외친 왕자를 제외
        arr.shift();
    }
  	// 마지막 남은 왕자 출력
    return arr[0];
}