[Algorithm] 큐(Queue) 자료구조

1. 큐(Queue)

 

큐는 선입선출(First In First Out, FIFO) 형태의 자료구조를 의미한다.

스택(stack)과 달리 제일 처음 들어간 데이터가 가장 먼저 나온다.

 

2. 문제

정보 왕국의 이웃 나라 외동딸 공주가 숲속의 괴물에게 잡혀갔습니다. 정보 왕국에는 왕자가 N명이 있는데 서로 공주를 구하러 가겠다고 합니다. 정보왕국의 왕은 다음과 같은 방법으로 공주를 구하러 갈 왕자를 결정하기로 했습니다.

왕은 왕자들을 나이 순으로 1번부터 N번까지 차례로 번호를 매긴다. 그리고 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;
    let queue = Array.from({ length: n }, (v, i) => i + 1);

    let num = 1;
    while (queue.length > 1) {
        if (num === k) num = 0;
        else queue.push(queue[0]);
        
        queue.shift();
        num++
    }

    return answer = queue[0];
}

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

 

위 문제는 큐를 활용하면 간단하게 풀이가 가능하다.

한 명의 왕자가 남을때까지 n명의 왕자들이 k번째 숫자를 말할때마다 제외하면 된다.

 

 

let queue = Array.from({ length: n }, (v, i) => i + 1);
//[1, 2, 3, 4, 5, 6, 7, 8]

 

우선 Array.from을 통해 queue를 만들어준다.

length(길이)는 n만큼, value는 index+1로 넣어준다.

 

그럼 1부터 8까지의 요소가 들어간 배열이 생성된다.

 

 

let num = 1;
while (queue.length > 1) {
   if (num === k) num = 0;
   else queue.push(queue[0]);
    
   queue.shift();
   num++
}

 

그 후 while문을 통해 한 명의 왕자가 남을때까지 반복문을 돌려준다

 

 

 

여기서 queue 개념을 활용하면 된다.

1명의 남자가 남을때까지 계속해서 숫자를 불러야 하기 때문에 배열은 계속해서 반복되어야 한다.

따라서 반복될때마다 맨 처음에 있는 왕자를 뒤로 넣어준다.

 

그리고 숫자 변수를 만든 후, 3이 될 때마다 맨 앞에 있는 왕자를 제외시켜준다

 

 

return answer = queue[0];

 

마지막으로 queue에 남아 있는 값을 answer에 넣어주면 된다.

 

 

 

*Array.from

 

Array.from은 문자열과 같은 유사 배열 객체(length 속성과 인덱싱 요소가 있는 객체)나

이터러블한 객체(순회 가능한 객체)를 배열로 만들어주는 메서드로 배열을 초기화할 때 사용한다. 

 

Array.from(arrayLike, mapFn, thisArg);

 

첫 번째 인자로는 배열로 변환할 이터러블 객체 또는 유사 배열 객체가 들어오고,

두 번째 인자로는 맵핑 함수가 들어온다.

 

mapFn은 배열에서 처리중인 현재 요소와 현재 요소의 인덱스를 매개변수로 받는다.