[Baekjoon Online Judge] 1934번: 요세푸스 문제

1158번: 요세푸스 문제

요구사항

 - 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다.

 - 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다.

 - 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 

입력

 - 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

출력

 - 예제와 같이 요세푸스 순열을 출력한다.

---

Queue를 활용하여 해결한다. 만약 3번째 사람을 제거한다고 가정한다.

 

1, 2, 3, 4, 5, 6, 7 로 총 7명의 사람이 원을 이루고 있다고 가정한다.

 

1, 2 는 1번째, 2번째 사람이기 때문에 제거하지 않는다. 단순히 뒤로 밀린다.

3, 4, 5, 6, 7, 1, 2 로 3이 제거된다.

4, 5, 6, 7, 1, 2 로 4와 5는 1번째, 2번째 이기 때문에 뒤로 밀린다.

6, 7, 1, 2, 4, 5 으로 3번째인 6이 제거된다.

 

이러한 과정을 반복한다. 즉 원을 그린사람들을 하나의 Queue로 가정하고 3번째 순서인 사람만 poll 하고, 아닌 사람들은 Quque에 다시 offer를 진행한다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class Baekjoon1158 {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = bufferedReader.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int k = Integer.parseInt(input[1]);

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

        for (int i = 1; i <= n; i++) queue.offer(i);

        StringBuilder stringBuilder = new StringBuilder("<");
        while (!queue.isEmpty()) {
            if (queue.size() == 1) {
                stringBuilder.append(queue.poll() + ">");
                break;
            }

            for (int i = 0; i < k - 1; i++) // k까지 제거한 후 queue의 뒤에 채운다.
                queue.offer(queue.poll());

            stringBuilder.append(queue.poll() + ", ");
        }

        bufferedWriter.write(stringBuilder.toString());

        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }
}