BOJ 1158 요세푸스 문제 (Java, Python)

큐 사용

• Java

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        String ans = "<";
        
        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
			q.offer(i);				// 1 ~ N 을 큐에 삽입
		}
        while (!q.isEmpty()) {
        	for(int i = 0; i < K - 1; i++) { // K번째 수 앞에 있는 수들을 뒤로
        		q.offer(q.poll());
        	}
			
			ans += q.poll();		// 앞에 와있는 K번째 수 삭제 및 반환
			if(q.size() != 0) {
				ans += ", ";
			}
		}
        System.out.println(ans + ">");
	}
}

• Python

from collections import deque

N, K = map(int, input().split())
ans = "<"

q = deque(list(range(1, N + 1)))

while q:
    for _ in range(K - 1):
        q.append(q.popleft())
    
    ans += str(q.popleft())
    if q:
        ans += ", "
    else:
        ans += ">"
    
print(ans)

리스트로 원형 큐 구현

• Python

N, K = map(int, input().split())
q = list(range(1, N + 1))
ans = []
head = 0

for i in range(N):
    head += K - 1			# 제거할 수의 인덱스
    if head >= len(q):		# 인덱스 범위를 벗어나면 나머지 연산
        head %= len(q)
    ans.append(q.pop(head))
    
print(str(ans).replace('[', '<').replace(']', '>'))