공주구하기(큐)

정보 왕국의 이웃 나라 외동딸 공주가 숲속의 괴물에게 잡혀갔습니다.
정보 왕국에는 왕자가 N명이 있는데 서로 공주를 구하러 가겠다고 합니다. 정보왕국의 왕은 다음과 같은 방법으로 공주를 구하러 갈 왕자를 결정하기로 했습니다.
왕은 왕자들을 나이 순으로 1번부터 N번까지 차례로 번호를 매긴다. 그리고 1번 왕자부터 N 번 왕자까지 순서대로 시계 방향으로 돌아가며 동그랗게 앉게 한다. 그리고 1번 왕자부터 시 계방향으로 돌아가며 1부터 시작하여 번호를 외치게 한다. 한 왕자가 K(특정숫자)를 외치면 그 왕자는 공주를 구하러 가는데서 제외되고 원 밖으로 나오게 된다. 그리고 다음 왕자부터 다시 1부터 시작하여 번호를 외친다.
이렇게 해서 마지막까지 남은 왕자가 공주를 구하러 갈 수 있다.

 

예를 들어 총 8명의 왕자가 있고, 3을 외친 왕자가 제외된다고 하자. 처음에는 3번 왕자가 3 을 외쳐 제외된다. 이어 6, 1, 5, 2, 8, 4번 왕자가 차례대로 제외되고 마지막까지 남게 된 7 번 왕자에게 공주를 구하러갑니다.
N과 K가 주어질 때 공주를 구하러 갈 왕자의 번호를 출력하는 프로그램을 작성하시오.

 

 

 

입력예제 1

8 3 

 

출력예제 1

7

 

 

 

function solution(n, k){
    let answer;

    // Array.from 을 이용해 매개변수(배열 길이) n값의 길이만큼의 인덱스 i + 1 값 (i는 0부터 시작이니) 로 채우는 배열을 생성한다.
    let queue=Array.from({length:n}, (v, i)=>i+1);

    //while 반복문을 사용해 queue.length 값이 0이 될때(false) 까지 반복문 생성
    while(queue.length){

        //삭제할 자리번호(k) 앞전까지 반복문 실행
        for(let i=1; i<k; i++) {

            //삭제할 자리번호(k) 앞전까지 맨앞 요소를 queue 배열에서 삭제 후 다시 집어넣는 행동을 반복 shift()는 배열 맨앞요소를 제거해준다.
            queue.push(queue.shift());
        }

        //위의 for문은 삭제할 자리번호(k) 앞전까지 반복문을 실행하니 여기서 shift()를 실행하면 해당 자리번호(k)가 삭제된다.
        queue.shift();

        //만약 queue 배열의 길이가 1이라면 answer에 queue.shift()를 사용해 마지막 배열요소를 저장하고,
        // 마지막 배열요소또한 shift()를 통해 제거되었으니 queue의 길이는 0이되어 while문을 탈출하게된다.
        if(queue.length===1) answer=queue.shift();
    }
    return answer;
}

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