백준 11866번 : 요세푸스 문제 0

---

이번 문제는 요세푸스 순열을 알고리즘으로 표현하는 문제이다.

말 그대로 표현하는 단계이기 때문에 복잡한 알고리즘은 없다.
그런데 요세푸스 문제를 처음 접해봤기 때문에 추후에 다시 만난다면 어떻게 해야하는 지 기억하기 위해 기록한다.

우선 요세푸스 순열은 양의 정수 두 개 n과 k가 주어질 때,
n 명의 사람이 원형으로 있고 해당 원에서 k 번째 마다 사람이 빠지는 형태이다.

즉, 원형으로 가정하고 k 번째 사람을 계속 골라내야한다는 뜻이다.

이 요세푸스 순열을 자바로 표현한다면 다음과 같다.

while (q.size() > 1) {
     for (int i = 0; i < k-1; i++) {
         q.add(q.poll());
     }
     q.poll();
}

이 알고리즘의 흐름은 다음과 같다.

1. 큐에 요소가 하나 남을 때 까지 반복한다.
2. k번 째에 도달할 때까지 앞의 요소를 빼고 뒤로 보낸다.
3. k번 째에 도달하면 해당 요소를 poll 한다.

원형으로 가정하고 큐를 사용하여 계속해서 k 번째에 도달할 때까지 순번을 뒤로 넘기는 형태이다.

n = 7, k = 3 이라고 가정하고 위의 알고리즘을 사용한 예시는 다음과 같다.

q = 1 2 3 4 5 6 7

2 3 4 5 6 7 1
3 4 5 6 7 1 2
poll -> 3
remain -> 4 5 6 7 1 2

5 6 7 1 2 4
6 7 1 2 4 5
poll -> 6
remain -> 7 1 2 4 5

1 2 4 5 7
2 4 5 7 1
poll -> 2
remain -> 4 5 7 1

이 예시를 보면 쉽게 이해할 수 있다.

요세푸스 순열 알고리즘을 활용한 전체 소스코드는 다음과 같다.

import java.io.BufferedReader;
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 java.io.IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        Queue<Integer> q = new LinkedList<>();

        for (int i = 1; i <= n; i++) {
            q.offer(i);
        }

        StringBuilder sb = new StringBuilder();
        sb.append("<");
        while (q.size() > 1) {
            for (int i = 0; i < k-1; i++) {
                q.add(q.poll());
            }
            sb.append(q.poll()).append(", ");
        }

        sb.append(q.poll()).append(">");
        System.out.println(sb);
    }
}

---

요세푸스 순열 공식은 크게 어려울 건 없지만 원형이라고 생각했을 때 큐를 어떤 식으로 표현해야할지 알게되었다. 또, 문제 제목에 0이라고 번호가 있기 때문에 다음에 또 마주칠 일이 있을 것 같다.