[큐] 공주 구하기

자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다.

 

 

 

 

📋 문제

괴물에게 잡힌 이웃나라의 공주를 구하기 위해 N명의 왕자가 나섰다.

공주를 구할 단 한 명의 왕자를 고르기 위해 왕은 다음과 같은 방법으로 공주를 구하러 갈 왕자를 고르기로 했다.

왕은 왕자들을 1부터 N까지 순서를 매겼다.

그리고 1번 왕자부터 시계방향으로 돌아가며 동그랗게 앉게 한 후 1부터 번호를 외치게 했다.

한 왕자가 특정한 숫자 K를 외치면 그 왕자는 공주를 구하러 가는 데서 제외되고 원 밖으로 나온다.

그리고 다음 왕자부터 다시 1부터 시작해 번호를 외친다.

이렇게 해서 마지막에 남은 왕자가 공주를 구하러 갈 수 있다.

 

 

예를 들어 8명의 왕자가 있고 3을 외친 왕자가 제외된다고 하면 제외되는 순서는 3, 6, 1, 5, 2, 8, 4가 되어 남은 왕자인 7번 왕자가 공주를 구하러 가게 된다.

 

왕자의 수인 N과 특정 숫자 K가 주어질 때 공주를 구하러 갈 왕자의 번호를 출력한다.

 

 

👉 입력

첫 번째 줄에 자연수 N과 K가 입력된다.

이때 N은 5 이상 1,000 이하의 수이며 K는 2이상 9 이하의 수이다.

 

 

👈 출력

첫 번째 줄에 마지막에 남은 왕자의 번호를 출력한다.

 

 

💡 사용된 개념

Queue(큐)

특수한 목적을 가지는 자료구조로 순서가 있는 entry들의 자료구조이다.

Queue는 FIFO(First-In, First-Out)의 구조로 저장된 data를 꺼낼 때 가장 먼저 들어간 data를 꺼낸다.

한쪽 끝에서는 추가, 한쪽 끝에서는 제거가 가능한 터널의 형태이다.

데이터를 queue에 삽입하는 과정을 enqueue, 추출하는 과정을 dequeue라고 한다.

js에서 enqueue 명령어는 push, dequeue 명령어는 shift이다.

 

 

Queue Error는 두 가지의 경우가 있다.

• Overflow : 이미 가득찬 Queue에 data를 추가적으로 삽입(enqueue)하려는 경우 발생하는 Error
• Underflow : 이미 비어있는 Queue에서 data를 추가적으로 빼내려는(dequeue) 경우 발생하는 Error

 

 

Array.from()

유사 배열 객체나 이터러블 객체를 얕게 복사해 새로운 Array 객체를 만든다.

 

Array.from(arrayLike[, mapFn[, thisArg]])

• arrayLike : 배열로 변환하고자 하는 유사 배열 객체나 이터러블 객체

 

 

📝 풀이

 

function solution(n, k) {
    let answer, count = 1;
    let queue = [];
    for (let i = 1; i <= n; i++) queue.push(i);
    while (queue.length !== 1) {
        if (count === k) {
            count = 1;
            queue.shift();
        }
        else {
            count++;
            let temp = queue.shift();
            queue.push(temp);
        }
    }
    answer = queue.shift();
    return answer;
}

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

 

먼저 for문을 돌며 queue에 1부터 n까지의 왕자들의 번호를 넣었다.

그리고 while문에서 1부터 숫자를 세는 작업을 한다.

 

count를 이용해 현재 외친 숫자가 특정 숫자 k가 아니라면 다음 숫자를 세고 이때 큐에 제일 먼저 들어가있던 data를 큐에서 빼내 다시 큐에 넣는다.

이 과정을 거치면 큐의 제일 앞에 있던 왕자의 번호가 큐의 제일 뒤에 위치하게 된다.

 

만약 count가 특정 숫자 k와 같다면 이 왕자는 원에서 빠져야 하니 count를 다시 1로 초기화하고 해당 왕자의 번호를 큐에서 아예 빼내준다.

그러면 점차 큐의 길이는 줄어들게 된다.

 

큐의 길이가 1이 되었을 때는 왕자가 1명 남았다는 이야기와 같으므로 while문을 빠져나오고 큐에 담겨있던 마지막 왕자의 번호를 answer에 넣어 리턴, 출력한다.

 

function solution(n, k) {
    let answer;
    let queue = Array.from({ length: n }, (v, i) => i + 1);
    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));

 

풀이는 같으나 서술하는 방식이 다르다.

우선 Array.from() 을 이용해 왕자의 번호들을 queue에 넣는다.

이후 queue.length가 0이 되면 while문을 빠져나오는 것을 이용해 숫자를 외치는 작업을 한다.

for문에서 1부터 특정 숫자 k까지 차례대로 번호를 외치게 하는데 k가 아니면 큐에서 빼낸 것을 다시 큐에 넣고 k면 큐에서 완전히 빼낸다.

 

이 과정을 거치면 점점 큐의 길이는 줄어들고 큐의 길이가 1이 되는 순간 큐에서 마지막 남은 하나를 빼 answer에 넣어준다.

큐의 길이가 0이 되고 while문을 빠져나오면 answer를 리턴, 출력한다.