[백준 11866 파이썬(Python) / 자바(Java)] 요세푸스 문제 0

백준(baekjoon) 11866 요세푸스 문제

문제 접근

처음에 문제를 접하고, 큐를 사용한 문제 풀이와 인덱스와 pop을 활용한 문제 풀이 2가지를 생각해보았다.

 

1. 파이썬(Python)

1) index와 pop을 이용한 문제 풀이

n, k = map(int, input().split())
arr = [i for i in range(1, n + 1)]
ans_arr = []

idx = k - 1  # 시작 인덱스를 K-1로 설정

while arr:
    # 인덱스가 배열의 길이를 초과하는 경우, 인덱스를 배열의 길이로 나눈 나머지로 조정
    if idx >= len(arr):
        idx %= len(arr)
    
    remove_elem = arr.pop(idx)
    ans_arr.append(remove_elem)

    # 다음 시작 인덱스를 K-1만큼 증가
    idx += k - 1

print("<", end="")
print(", ".join(map(str, ans_arr)), end="")
print(">")

 

2) queue 자료구조를 활용한 문제 풀이(FIFO)

from collections import deque

def josephus_permutation(n, k):
    queue = deque(range(1, n + 1))  # 1부터 N까지의 숫자로 큐 초기화
    result = []
    
    while queue:
        for _ in range(k - 1):  # K-1번째까지의 요소를 큐의 맨 뒤로 이동
            queue.append(queue.popleft())
        
        result.append(queue.popleft())  # K번째 요소를 결과 리스트에 추가
    
    return result

# 입력 받기
n, k = map(int, input().split())

# 요세푸스 순열 생성
permutation = josephus_permutation(n, k)

# 결과 출력
print("<", end="")
print(*permutation, sep=", ", end="")
print(">")

print(*permutation, sep=", ", end="")

-> `*`은 iterable 객체를 언패킹(unpacking)하는 역할
print() 함수는 여러 개의 인수를 받을 수 있으며, 인수들을 공백으로 구분하여 출력한다.
*를 사용하면 iterable 객체인 permutation을 개별 요소로 언패킹하여 print() 함수의 인수로 전달한다.

예를 들어, permutation이 [3, 6, 2, 7, 5, 1, 4]와 같은 리스트라고 가정하자.

print(permutation)은 아래의 결과를 출력한다.

[3, 6, 2, 7, 5, 1, 4]

print(*permutation)은 아래의 결과를 출력한다.

3 6 2 7 5 1 4

따라서 `*`는 리스트, 튜플 등의 요소를 각각 개별적으로 처리할 수 있는 역할을 한다.

 

2. 자바(Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Queue<Integer> q = new LinkedList<>();

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int n = Integer.parseInt(st.nextToken()); // 입력 받은 정수 n
        int k = Integer.parseInt(st.nextToken()); // 입력 받은 정수 k

        for (int i = 1; i <= n; i++) {
            q.add(i); // 큐에 1부터 n까지의 수를 추가
        }

        StringBuilder sb = new StringBuilder();
        sb.append('<');

        while (q.size() > 1) {
            for (int i = 0; i < k - 1; i++) {
                q.offer(q.poll()); // 큐에서 맨 앞의 원소를 빼서 맨 뒤로 보냄
            }

            sb.append(q.poll()).append(", "); // k번째 원소를 큐에서 빼고 출력 문자열에 추가
        }

        sb.append(q.poll()).append('>'); // 마지막으로 남은 원소를 출력 문자열에 추가
        System.out.println(sb); // 결과 출력
    }
}