백준 자바스크립트 - 요세푸스 문제

1. 백준 - '#1158'

 

1) 문제

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

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

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

 

2) 입출력 예

 

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

 

3) 코드

consft fs = require("fs");

const readFileSyncAddress = "input.txt";

const input = fs.readFileSync(readFileSyncAddress).toString().trim().split("\n");

// 예제 문자열로 배열에 집어 넣음
const [n, k] = input[0].split(' ');

//문제풀이
function solution(n, k) {
	const queue = [];
    const answer = [];
    // 포문돌려서 queue에 쌓는다. 우리가 아는 큐가 아니라 배열 이름이 queue임.
    for (let i = 0; i<n; i+=1) queue.push(i + 1);
   
    let count = 1;
    while (queue.length) {
    // queue의 맨 앞부터 꺼낸다.(배열의 크기가 0될때까지)
    	const shiftItem = queue.shift();
        if(count % k === 0) {
    // k번째라면 answer 배열에 push
        	answer.push(shiftItem);
            } else {
    // 아니면 queue에 push.
            	queue.push(shiftItem);
            }
            count += 1;
        }
        console.log(`<${answer.join(', ')}>`);
    }
    
    // 제출
    solution(n, k);
    // for문 돌리거나 while돌려서 하는 풀이가 대부분임.
    // 왼쪽부터 쌓는다면(진짜 큐라면) pop써서 뒤에꺼부터 꺼내면 됨.
    // 오른쪽에서 쌓아준다면 shift써서 앞쪽부터 꺼내서 확인한다.

코드 출처: https://junghyeonsu.tistory.com/241