[JS] 코딩 테스트 문제 : 공주 구하기 [큐]

문제 : 공주 구하기

문제 설명

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

왕은 왕자들을 나이 순으로 1번부터 N번까지 차례로 번호를 매긴다. 그리고 1번 왕자부터 N 번 왕자까지 순서대로 시계 방향으로 돌아가며 동그랗게 앉게 한다. 그리고 1번 왕자부터 시계방향으로 돌아가며 1부터 시작하여 번호를 외치게 한다. 한 왕자가 K(특정숫자)를 외치면 그 왕자는 공주를 구하러 가는데서 제외되고 원 밖으로 나오게 된다. 그리고 다음 왕자부터 다시
1부터 시작하여 번호를 외친다.

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

예를 들어 총 8명의 왕자가 있고, 3을 외친 왕자가 제외된다고 하자. 처음에는 3번 왕자가 3 을 외쳐 제외된다. 이어 6, 1, 5, 2, 8, 4번 왕자가 차례대로 제외되고 마지막까지 남게 된 7 번 왕자에게 공주를 구하러갑니다.

N과 K가 주어질 때 공주를 구하러 갈 왕자의 번호를 출력하는 프로그램을 작성하시오.

▣ 입력설명

첫 줄에 자연수 N(5<=N<=1,000)과 K(2<=K<=9)가 주어진다.

▣ 출력설명

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

▣ 입력예제 1

8 3

▣ 출력예제 1

7

내코드

// 일반적인 배열을 수정해나가는 방식
function solution(n, k) {
  let answer;
  let arr = Array.from({ length: n }, (v, i) => i + 1);
  let current = k - 1; // 삭제될 배열의 인덱스를 의미

  // 배열의 길이 - 1 만큼 순회
  for (let index = 1; index < n; index++) {
    console.log("### 현재 기준 인덱스: ", current);
    console.log("### 제외 전 배열 상황: ", ...arr);
    //arr.splice(current, 1) 왕자를 제외하여 배열을 변경
    console.log("### 제외된 왕자 번호: ", arr.splice(current, 1));
    console.log("### 제외 후 배열 상황: ", ...arr);
    console.log("---------------------------------------------");

    // 삭제 된후 current 인덱스 값이 변경된 배열의 길이와 같다면 다음 왕자인 0번째로 이동
    if (current === arr.length) {
      current = 0;
    } else {
      current += k - 1; // 인덱스 변경
      // 마찬가지로 배열의 길이를 넘어가면 배열의 길이 만큼 뺀 즉 다음 왕자의 인덱스를 가르킴
      if (current >= arr.length) current -= arr.length;
    }    
  }
  answer = arr.pop();
  return answer;
}

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

풀이

1. 제외될 왕자의 인덱스 번호를 나타낼 변수 current 의 초기값으로 k-1 로 초기화
2. 열의 길이 - 1 만큼 순회하면서 splice 메서드를 통해 배열의 current 인덱스의 왕자 번호를 배열에서 제외
3. 제외한 이후 만큼 이동 후 만약 이동 중에 배열의 길이를 벗어나면 첫 번째 인덱스로 이동해서 처리
4. current 인덱스 k-1 만큼 증가 시켜 다음 제외될 왕자의 인덱스로 변경 만약 배열의 길이를 넘어갈 시 배열의 길이만큼 빼서 처리 다음 왕자 인덱스를 가르키게 됨
5. 마지막으로 남은 왕자의 번호를 배열에서 pop 하면서 마지막 남은 왕자의 번호를 반환

다른 해결 방법

// que 를 활용한 방법 (답안지 내용)
function solution(n, k) {
  let answer;
  let queue = Array.from({ length: n }, (v, i) => i + 1);

  // 아이디어
  // 원형 큐라고 생각하고 front(삭제위치) 의 k 번째 전까지 왕자를 다시 rare(삽입위치) 에 붙인다.
  // k 번째 왕자는 제외된 후 그다음 새로운 front 에서 마찬가지로 위 과정을 반복하다.
  // 예) [1,2,3,4,5] -> [3,4,5,1,2] 선형 배열구조를 원형으로 생각하면 결국 1번부터 5번까지 왕자들의 순서는 바뀌지 않는다
  while (queue.length) {
    // k 번째 전까지 제외하고 다시 배열의 마지막에 붙임
    for (let i = 1; i < k; i++) {
      queue.push(queue.shift());
      console.log("위치조정: ", queue);
    }
    // 위과정에서 k - 1 번 만큼 위치를 조정했기 때문에 현재 queue 배열에 첫번째 왕자가 k 번째 왕자를 의미하므로 제외시킨다.
    console.log(`k 번째 왕자 '${queue.shift()}' 제외 후 결과: `, queue);

    // 모두제외되고 마지막 남은 왕자번호를 저장
    if (queue.length === 1) answer = queue.shift();
  }
  return answer;
}

풀이

※ 왕자들의 번호를 담긴 배열을 원형 큐로 바라보고 처리하는 방식

1. queue.length 를 기준으로 반복문을 열고
2. 반복문 안에서 다시 k-1 만큼 왕자들을 front(삭제위치) 에서 다시 rare(삽입위치) 에 붙인 이후 shift 하여 현재 왕자 번호를 완전히 제외
3. 반복문 안에서 배열의 길이가 1 인 경우 반복문을 마치고 그 번호를 반환

---

참고

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/dashboard