Queue 자료구조

Q. 1~8번까지의 번호가 있다. 여기서 3번째에 해당하는 숫자는 삭제되고 마지막으로 남는 번호는?

    예를 들어, 3이 삭제되고 나면 4번이 1번이 되며 세번째에 해당하는 6번이 삭제된다.

 

A.

큐 자료구조를 사용한다.

먼저 1~8번을 배열에 넣어주고, 1,2번과 같이 삭제되지 않아도 되는 데이터들을 배열의 마지막부분에 넣어준다.

arr=[1,2,3,4,5,6,7,8]를 arr=[4,5,6,7,8,1,2] 이런식으로!

function solution(n, k) {
  let answer;
  let queue = Array.from({ length: n }, (v, i) => i + 1); //1~8번까지 배열 만들어주기
  while (queue.length > 0) {
    for (let i = 1; i < k; i++) queue.push(queue.shift()); //2번째까지는 다시 배열에 넣어주기
    queue.shift();
    if (queue.length === 1) {
      answer = queue.shift();
    }
  }
  return answer;
}

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

[해결]

Array.from을 사용해서 1~8번에 해당하는 배열을 하나 새로 생성해준다.

그리고 queue안에 데이터가 0보다 많을때까지 while을 반복한다.

그 안에서 for문이 k 전까지 즉, 2번째 까지 돌고 3번째 하나는 삭제한다.(shift) , + 2번째까지 돈 데이터는 다시 배열에 넣어준다.
while문이 도는 동안 queue안에 length===1 데이터가 하나만 남았다면 answer에 마지막값을 넣어준다.

**shift는 삭제된 값을 반환하므로 answer에 넣어준다.