[백준] 11866 : 요세푸스 문제 0

728x90

SMALL

https://www.acmicpc.net/problem/11866

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

512 MB

98860

56598

47374

56.807%

문제

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

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 ≤ 1,000)

출력

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

예제 입력 1 복사

7 3

예제 출력 1 복사

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

Code

const fs = require('fs'); //fs 모듈 사용
const [N, K] = fs.readFileSync('/dev/stdin').toString().trim().split(' ').map(Number);

const arr = [];
for (let i = 1; i <= N; i++) arr.push(i);

const result = [];
let idx = 0;

while (arr.length > 0) {
    idx = (idx + K - 1) % arr.length; // K번째 사람의 인덱스
    result.push(arr.splice(idx, 1)[0]); // 제거하고 결과에 추가
}

console.log('<' + result.join(', ') + '>');

Code 풀이

const fs = require('fs');
const [N, K] = fs.readFileSync('/dev/stdin').toString().trim().split(' ').map(Number);

fs 모듈을 불러옵니다.
표준 입력을 한 번에 읽어서 문자열로 변환하고, 앞뒤 공백을 제거합니다.
.split(' ')로 공백 기준으로 나눠서 배열로 만듭니다. 예: 입력이 "7 3"이면 ["7", "3"]
.map(Number)로 각 요소를 숫자로 변환합니다. → N = 7, K = 3

const arr = [];
for (let i = 1; i <= N; i++) arr.push(i);

1부터 N까지의 숫자를 배열 arr에 저장합니다.
예: N=7이면 arr = [1, 2, 3, 4, 5, 6, 7]

const result = [];
let idx = 0;

result: 요세푸스 순열(제거되는 순서)을 저장할 배열입니다.
idx: 현재 제거할 사람의 인덱스를 저장할 변수입니다.

while (arr.length > 0) {
    idx = (idx + K - 1) % arr.length; // K번째 사람의 인덱스
    result.push(arr.splice(idx, 1)[0]); // 제거하고 결과에 추가
}

배열에 사람이 남아있는 동안 반복합니다.
idx = (idx + K - 1) % arr.length;
- 현재 위치에서 K-1만큼 이동해서 K번째 사람의 인덱스를 구합니다.
- % arr.length는 원형(끝에서 다시 처음으로 돌아감)을 구현합니다.
- 예시로 이해하기
예시 1: N=7, K=3, 처음 idx=0
- arr: [1, 2, 3, 4, 5, 6, 7]
- idx = (0 + 3 - 1) % 7 = 2 % 7 = 2
- → 2번 인덱스(3번째 사람, 값은 3)를 제거
arr.splice(idx, 1)[0] // idx 위치에서 1개 삭제
- arr에서 idx 위치의 사람을 제거하고, 그 값을 반환합니다.
- 제거된 사람을 result에 추가합니다. ( arr.splice(idx, 1)의 결과 배열에서 첫 번째(0번째) 값을 꺼내서 result에 추가한다는 뜻)

예시 (N=7, K=3)

arr: [1,2,3,4,5,6,7], idx=0
idx = (0+3-1)%7 = 2 → 3 제거 → result: [3], arr: [1,2,4,5,6,7]
idx = (2+3-1)%6 = 4 → 6 제거 → result: [3,6], arr: [1,2,4,5,7]
idx = (4+3-1)%5 = 1 → 2 제거 → result: [3,6,2], arr: [1,4,5,7]
idx = (1+3-1)%4 = 3 → 7 제거 → result: [3,6,2,7], arr: [1,4,5]
idx = (3+3-1)%3 = 2 → 5 제거 → result: [3,6,2,7,5], arr: [1,4]
idx = (2+3-1)%2 = 0 → 1 제거 → result: [3,6,2,7,5,1], arr: [4]
idx = (0+3-1)%1 = 0 → 4 제거 → result: [3,6,2,7,5,1,4], arr: []

console.log('<' + result.join(', ') + '>');

result 배열을 , 로 이어붙여서 < >로 감싸 출력합니다.
예: <3, 6, 2, 7, 5, 1, 4>

정리

1부터 N까지 배열에 저장
K번째 사람을 계속 제거해서 그 순서를 기록
원형 큐처럼 인덱스를 계산해서 제거
마지막에 요세푸스 순열을 < >로 출력