[백준 9012번 요세푸스 문제 - node.js] [알고리즘 기초 1/2]

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

1158번: 요세푸스 문제

 

문제

 

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

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)

 

출력

 

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

 

예제 입출력

 

입력	출력
7 3	<3, 6, 2, 7, 5, 1, 4>

풀이[node.js]

 

 

728x90

요세푸스의 수열이라는 개념을 이용하여 로직을 구현하였습니다.

우선 N의 길이만큼 배열 arr에 값을 넣어주었습니다. ([1, 2, 3, 4, 5, 6, 7])

그리고 arr 배열을 돌면서 m이 k번째 값까지 갈 때까지 arr를 돌리는데요.

만약 이 m이 k와 같지 않다면, arr의 가장 앞의 값을 제거하고 배열의 가장 뒤에 push를 해주고, m이 k와 같은 값이라면, arr에서 값을 제거해주고 그 값을 deleted라는 배열에 push 해줍니다.

이렇게 되면, k번째 값인 3번째 값들은 계속 deleted에 쌓이게 되고, arr는 k번째 값을 제외한 값들이 배열의 가장 뒤에 순서대로 쌓이게 됩니다.

이런 방식으로 일차원이 배열을 마치 원형인 배열인 것처럼 연속되도록 사용할 수 있습니다.

 

그리고 가장 마지막에 answer값의 형식을 늘 주의해야합니다.

저도 deleted된 배열을 그냥 join()을 사용해서, <3,6,2,7,5,1,4> 이렇게 값이 나와서 틀렸었는데, join(', ')로 공백을 추가해주어야 합니다!

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().split(' ');
var n = parseInt(input[0]);
var k = parseInt(input[1]);
var arr = [];
var answer = '';
var deleted = [];
for(var i=0; i<n; i++){
    arr[i] = i+1;
}
for(j=0; j<n; j++){
    for(var m=1; m<=k; m++){
        if(m === k){
            deleted.push(arr.shift());
        }else{
            arr.push(arr.shift());
        }
    }
}
answer = '<' +deleted.join(', ') + '>';
console.log(answer);