[인프런 섹션6] 공주 구하기 (Javascript)

👩🏻‍💻문제링크

[인프런 섹션6] 공주 구하기 (Javascript)
유료 강의인 관계로 문제 설명은 생략합니다.

✍️Idea Sketch

2021-06-27 queue를 사용하는 문제임을 늦게 파악

첫번째 시도 : stack 사용

1. 왕자가 특정숫자 K를 외치면 제외, 처음부터 시작

2. stack 을 생성하여 초기값 1, 제외되면 0

let stack = Array.from({length: n}, v => 0);

3. 왕자 제외 로직

• stack 값이 1인 경우, num++
• num === k 인 경우 stack 값은 0, num === 0;

성능 이슈 예측
수많은 왕자가 제외된 상황에서도 stack을 처음부터 끝까지 순회

문제점
마지막 남은 왕자를 출력해야 함
매번 1인 stack값이 몇 개인지 확인해야 함

4. stack에 1번부터 n번까지 초기값 설정

let stack = Array.from({length: n-1}, (v, i) => i+1);

5. k를 외친 왕자는 stack.pop();

• while (stack.length > 1)
• stack 순회하다가 중간에 값을 삭제하므로 stack이라 할 수 없군. stack이 아니네

---

1. stack에 1번부터 n번까지 초기값 설정 [1, 2, 3, … , n]

let stack = Array.from({length: n-1}, (v, i) => i+1);

2. for문으로 stack을 순회

• 순회할 때마다 newStack.push(); num++
• num === k인 경우 num = 0;
• stack 한바퀴 순회한 경우, stack = newStack 설정

문제점
javascript 특성상 배열 복사 arr.slice()를 써야하는데, 안쓸 수 없나?

---

두번째 시도 : queue 사용

1. queue 1번부터 n번까지 초기값 설정 [1, 2, 3, … , n]

let queue = Array.from({length: n-1}, (v, i) => i+1);

2. queue 순회

• 순회할 때마다 cnt++, queue.push(queue.shift());
• cnt === k 인 경우 cnt = 0, queue.shift();

while (queue.length > 1) {
    let num = queue.shift();

    if (cnt === k) cnt = 0;
    else {
        queue.push(num);
        cnt++;
    }
}

return queue.shift();

✍️소스코드

2021-06-27

function solution(n, k) {
    let queue = Array.from({length: n}, (v, i) => i+1);
    let cnt = 0;

    while (queue.length > 1) {
        let num = queue.shift();
        cnt++;

        if (cnt === k) cnt = 0;
        else queue.push(num);
    }

    return queue.shift();
}