[Baekjoon] 1158 요세푸스 문제(파이썬/자바스크립트/NodeJS)

이번 문제는 아래 링크에서 풀어볼 수 있습니다.

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)

출력

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

예제 입력 1

7 3

예제 출력 1

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

 

---

정답 코드

나의 코드(오답)

import sys

n, k = map(int, sys.stdin.readline().rstrip().split())


def mySolution(n, k):
    nums = []
    result = []
    
    for num in range(1, n + 1):
        nums.append(num)

    idx = k - 1

    while nums:
        left = []
        right = []
        if len(nums) >= k:
            popped = nums.pop(idx)
            result.append(str(popped))
            for i in range(idx, len(nums)):
                left.append(nums[i])
            for i in range(0, idx):
                right.append(nums[i])
            nums = left + right
        else :
            popped = nums.pop(0)
            result.append(str(popped))
            for num in nums:
                left.append(num)
            nums = left

    return f"<{', '.join(result)}>"

    
    
print('mySolution', mySolution(n, k))

답안 1
파이썬 Ver.

from collections import deque
import sys

n, k = map(int, sys.stdin.readline().rstrip().split())

def answer1(n, k):
    people = deque()
    for i in range(1, n+ 1): people.append(i)
    result = []

    while people:
        for _ in range(k - 1):
            people.append(people.popleft())
            
        result.append(people.popleft())
    
    return str(result).replace('[', '<').replace(']', '>')

print('answer1', answer1(n, k))

자바스크립트/NodeJS Ver.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs
    .readFileSync(filePath)
    .toString()
    .trim()
    .split(' ')
    .map((val) => parseInt(val));

const [n, k] = input;

const answer1 = (n, k) => {
    const people = [];
    for (let i = 1; i <= n; i++) people.push(i);
    const result = [];

    while (people.length) {
        for (let i = 0; i < k - 1; i++) {
            people.push(people.shift());
        }
        result.push(people.shift());
    }

    return `<${result.map((val) => String(val)).join(', ')}>`;
};

console.log('answer1', answer1(n, k));

답안 2
파이썬 Ver.

import sys

n, k = map(int, sys.stdin.readline().rstrip().split())

def answer2(n, k):
    people = [i for i in range(1, n + 1)]
    result = []
    idx = 0
    
    for _ in range(n):
        idx += k - 1
        
        if idx >= len(people):
            idx %= len(people)
            
        result.append(str(people.pop(idx)))
    
    return f"<{', '.join(result)}>"
  
print('answer2', answer2(n, k))

 

자바스크립트/NodeJS Ver.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs
    .readFileSync(filePath)
    .toString()
    .trim()
    .split(' ')
    .map((val) => parseInt(val));

const [n, k] = input;

const answer2 = (n, k) => {
    const people = [];
    for (let i = 1; i <= n; i++) people.push(i);
    const result = [];

    let idx = 0;

    for (let i = 0; i < n; i++) {
        idx += k - 1;

        if (idx >= people.length) {
            idx %= people.length;
        }

        result.push(people.splice(idx, 1)[0]);
    }

    return `<${result.map((val) => String(val)).join(', ')}>`;
};

console.log('answer2', answer2(n, k));

답안 3

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs
    .readFileSync(filePath)
    .toString()
    .trim()
    .split(' ')
    .map((val) => parseInt(val));

const [n, k] = input;

const answer3 = (n, k) => {
    const queue = [...new Array(n)].map((item, index) => (item = index + 1));
    const result = [];
    let count = 1;

    while (queue.length) {
        const shifted = queue.shift();

        if (count % k === 0) {
            result.push(shifted);
        } else {
            queue.push(shifted);
        }

        count++;
    }

    return `<${result.map((val) => String(val)).join(', ')}>`;
};

console.log('answer3', answer3(n, k));

답안 4

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs
    .readFileSync(filePath)
    .toString()
    .trim()
    .split(' ')
    .map((val) => parseInt(val));

const [n, k] = input;

const answer4 = (n, k) => {
    const arr = Array.from({ length: n }, (v, i) => i + 1);
    const result = [];

    for (let i = 0; i < n; i++) {
        for (let j = 1; j <= k; j++) {
            if (j === k) {
                result.push(arr.shift());
            } else {
                arr.push(arr.shift());
            }
        }
    }

    return `<${result.map((val) => String(val)).join(', ')}>`;
};

console.log('answer4', answer4(n, k));

답안 5

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs
    .readFileSync(filePath)
    .toString()
    .trim()
    .split(' ')
    .map((val) => parseInt(val));

const [n, k] = input;

const answer5 = (n, k) => {
    const arr = Array.from({ length: n }, (v, i) => i + 1);
    const result = [];

    let cnt = 0;

    while (arr.length) {
        cnt = (cnt + k - 1) % arr.length;
        result.push(arr[cnt]);
        arr.splice(cnt, 1);
    }

    return '<' + result.join(', ') + '>';
};

console.log('answer5', answer5(n, k));

---

문제 풀이

 나의 경우 인덱스를 기준으로 해당 값을 pop하여 정답 배열에 넣고 인덱스를 기준으로 리스트를 왼쪽, 오른쪽으로 나눈 다음 위치를 바꿔 합치는 식으로 접근했다. 이처럼 복잡하게 계산할 필요 없이 자료구조 중 큐를 활용한다면 쉽게 풀 수 있는 문제다. 

 답안 1을 예로 들자면 while 반복문을 돌면서 사람을 한 명씩 제거해나간다. 이때 k번째 바로 앞의 요소까지를 큐의 맨 뒤로 보내면 k번째 요소가 맨 앞으로 오게 되는데 이 k번째 요소를 정답 리스트에 쌓아나간다.

# k = 3을 예로 들자면
# for _ in range(k - 1)을 했을 경우 for 반복문은 2번 실행됨.
# [1, 2, 3, 4, 5, 6, 7] 1과 2가 리스트의 맨 끝에 차례로 삽입됨
# [3, 4, 5, 6, 7, 1, 2] for 반복문을 거친 뒤 큐는 다음과 같이 된다. 여기서 맨 앞의 요소, 즉 k번째 요소인 3을 결과 리스트에 쌓는다.

 이렇게 큐 people의 k번째 요소가 result 리스트에 쌓이면 반복문을 빠져나와 결괏값을 출력한다.

---

함께 보기

https://infinitt.tistory.com/213

백준 (boj) 파이썬 - 1158 요세푸스 문제

https://velog.io/@thguss/%EB%B0%B1%EC%A4%80-1158.-%EC%9A%94%EC%84%B8%ED%91%B8%EC%8A%A4-with.-Python-%ED%81%90-%EB%AC%B8%EC%A0%9C%EC%97%90%EC%84%9C-deque%EB%8A%94-%ED%95%84%EC%88%98-%EB%B3%84%EA%BC%AC%EB%A6%AC-%EB%95%85%EB%95%85

백준 1158. 요세푸스 (with. Python) - 큐 문제에서 deque()는 필수 별꼬리 땅땅

https://velog.io/@rkio/%EB%B0%B1%EC%A4%80-Javascript-1158

https://rrecoder.tistory.com/197