자료구조(큐) - 6. 공주구하기

문제

왕자가 N명이 있다.
1번 왕자부터 시작하여 1부터 번호를 외친다.
한 왕자가 k(특정숫자)를 외치면 그 왕자는 제외시킨다.
그리고 다음 왕자부터 다시 1부터 시작하여 번호를 외친다.
마지막까지 남은 왕자가 공주를 구하러 갈 수 있는 함수를 작성하시오시오.

입력예제 1
N= 8,  K= 3

출력예제 1
7

 

 

풀이

 

1. 마지막 요소를 담을 answer 변수 선언

2. queue를 담을 변수 선언

3. queue 를 n길이 만큼 숫자를 넣음

4. queue 길이가 0이 될때까지 while 반복문을 돌림

4-1. k-1번 만큼 반복문을 돌리면서 맨앞 요소를 맨뒤로 옮겨줌

4-2. 맨 앞 요소를 꺼냄

4-3 만약 queue의 길이가 1이되면 answer에 queue.shift() 함.

5. answer를 리턴함

위의 풀이방식에 따른 queue의 배열 상태

 

코드

<script>
function solution(n, k) {
  let answer;
  let queue;
  queue = Array.from({length: n}, (v, i) => i+1);
  console.log(queue);

  while(queue.length) {
    for (let i = 1; i < k; i++) queue.push(queue.shift());
    queue.shift();
    if (queue.length === 1) answer = queue.shift();
  }

  return answer;
}

console.log(solution(8, 3));
</script>

 

 

출처

자바스크립트 알고리즘 문제풀이(코딩테스트 대비) - 인프런 | 강의