[JavaScript] 백준 1158번 요세푸스 문제

이 글은 백준 1158번 요세푸스 문제를 풀이한다. 코드는 JavaScript로 구현하였다.

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

예제 입력 1

7 3

예제 출력 1

<3, 6, 2, 7, 5, 1, 4>

제한

• 시간: 2초
• 메모리: 256MB

풀이

접근

이 문제에서는 N과 K가 주어지면 (N, K) - 요세푸스 순열을 구하는 것이 목표이다.

 

예를 들어, N이 7이고 K가 3이라면 다음과 같은 과정을 거쳐 (7,3)-요세푸스 순열을 구한다.

• 1 2 3 4 5 6 7 (초기 상태)
• 1 2 X 4 5 6 7 (3번째 사람 제거)
• 1 2 X 4 5 X 7 (6번째 사람 제거)
• 1 X X 4 5 X 7 (2번째 사람 제거)
• 1 X X 4 X X 7 (5번째 사람 제거)
• 1 X X 4 X X X (1번째 사람 제거)
• X X X 4 X X X (4번째 사람 제거)

따라서 (7,3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>가 된다.

 

코드의 주요 로직은 다음과 같다.

1. 1부터 N까지의 숫자를 담을 배열 생성
2. 제거 할 배열의 요소를 가리킬 역할을 하는 포인터 변수 생성 (초기값 -1)
3. N이 0보다 큰 동안 다음을 반복 (아직 제거할 사람이 남아있는 동안 반복)
4. "canMove"라는 변수를 K로 설정 (포인터가 이동할 수 있는 거리)
5. "canMove"가 0보다 큰 동안 다음을 반복 (포인터가 이동하는 과정)
6. 포인터를 (index + 1) % N 으로 업데이트하여 다음 위치로 이동 (포인터가 원형으로 순환하며 이동)
7. "canMove"를 1 감소
8. "canMove"를 모두 소진했을 경우 제거되는 사람의 번호를 요세푸스 순열 배열에 저장
9. 포인터 1 감소 (배열의 크기가 줄어들었으므로 포인터도 이에 맞게 감소)
10. N을 1 감소 (제거되고 난 뒤 남은 사람의 수)
11. N이 0이 될 때까지 3번부터 10번까지의 과정을 반복
12. 요세푸스 순열 배열을 문자열로 변환하여 출력

구현

내가 구현한 코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";

// 입력 값 받기
let [N, K] = fs.readFileSync(filePath).toString().split(" ").map(Number);

// 변수 선언
const yoseArr = []; // 요세푸스 순열을 저장할 배열
const humanArr = []; // 사람들의 번호를 저장할 배열
for (let i = 1; i <= N; i++) {
  humanArr.push(i);
}
let index = -1; // humanArr 포인터

// K번째 사람 제거 반복
while (N > 0) {
  let canMove = K; // 포인터가 이동할 수 있는 거리
  while (canMove > 0) {
    index = (index + 1) % N;
    canMove--;
  }
  yoseArr.push(humanArr[index]);
  humanArr.splice(index, 1);
  index--;
  N--;
}

// 요세푸스 순열 출력
let yoseArrString = "<";
yoseArrString += yoseArr.join(", ");
yoseArrString += ">";
console.log(yoseArrString);

GPT 코드 리뷰

코드 구조의 개선

내가 푼 코드는 전체 로직을 한 곳에 집중하여 작성하였지만, GPT가 제안한 코드는 함수로 분리하여 구조화하였다. 함수를 사용하면 코드를 논리적으로 분리할 수 있으며, 재사용성과 가독성을 개선할 수 있다.

splice() 메서드로 인한 성능 저하

내가 푼 코드에서는 1부터 N까지의 번호를 저장하는 배열을 동적으로 생성했다.
이 경우에는 'splice' 메서드를 사용하여 요소를 제거할 때 배열의 구조를 변경해야 한다.
배열의 요소를 제거하고 나면 배열의 빈 공간을 메우기 위해 요소들을 이동시켜야 한다.
이러한 작업은 배열의 크기에 따라 비용이 증가하므로, 요소를 제거할 때마다 성능 저하가 발생할 수 있다.

반면에, GPT가 제안한 코드에서는 배열을 정적으로 생성했다.
이 경우에는 배열의 구조를 동적으로 변경하지 않고 초기에 한 번만 배열을 구성하면 되기 때문에 성능이 개선될 수 있다.

따라서 'splice' 메서드를 사용하여 배열의 구조를 변경하는 작업을 최소화할 수 있는 정적 배열 생성 방식이 동적 배열 생성 방식보다 성능상 이점을 가질 수 있다.

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";

// 입력 값 받기
let [N, K] = fs.readFileSync(filePath).toString().split(" ").map(Number);

// 요세푸스 순열 계산
const josephusPermutation = (N, K) => {
  const people = Array.from({ length: N }, (_, index) => index + 1); // 1부터 N까지의 숫자 배열 생성
  const yoseArr = []; // 요세푸스 순열을 저장할 배열
  let index = 0;

  while (people.length > 0) {
    index = (index + K - 1) % people.length;
    yoseArr.push(people.splice(index, 1)[0]);
  }

  return yoseArr;
};

// 요세푸스 순열 출력
const result = josephusPermutation(N, K);
const yoseArrString = `<${result.join(", ")}>`;
console.log(yoseArrString);

성능 비교

GPT가 풀어준 코드가 메모리, 시간 면에서 성능이 향상됐다.