[BOJ] 11866. 요세푸스 문제 0

문제 원본 : https://www.acmicpc.net/problem/11866

11866번: 요세푸스 문제 0

import java.util.Arrays;
import java.util.Scanner;

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

        int[] arr = new int[n];
        Arrays.fill(arr, 1);

        StringBuffer buffer = new StringBuffer();
        buffer.append("<");

        int cnt = 1;
        int j = 0;
        for (int i = 0; i < n; ++i) {
            for (; ; ++j) {
                if (arr[j % n] == 1) {
                    if (cnt == k) {
                        if (i == n - 1) {
                            buffer.append(j % n + 1);
                        } else {
                            buffer.append(j % n + 1 );
                            buffer.append(", ");
                        }
                        cnt = 1;
                        arr[j % n] = 0;
                        break;
                    }
                    ++cnt;
                }
            }
        }

        buffer.append(">");
        System.out.println(buffer.toString());
    }
}

• N이 작아서(1000) 그냥 무식하게 풀었다.
• 시간 복잡도가 O(n^2)이기 때문에 N이 조그만 커져도 못 써먹을 알고리즘이다...
• 최적화를 해야 하는 문제가 있기 때문에 그 문제를 풀 때 다시 고민해봐야겠다.