[Java] BOJ 11866: 요세푸스 문제, 큐

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

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

public class Problem11866 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            q.add(i);
        }

        System.out.print("<");

        while (q.size() > 1) {
            for (int i = 1; i < k; i++) {
                q.add(q.poll());
            }
            System.out.print(q.poll() + ", ");
        }

        System.out.print(q.poll() + ">");
    }
}

---

▶ 문제를 보자마자 일단 큐가 생각났고, 그래서 큐를 사용해 직접 풀어보았다. 그런데 요세푸스 문제에 대해 찾아보니, 큐를 사용하는 방법 외에도 좋은 방법들이 많았다. 지금 내가 작성한 코드는 시간복잡도가 O(n * k)이므로 효율적인 알고리즘은 아니라고 판단한다. 추후 개선된 코드로 다시 작성하도록 하겠다.