[백준] 1158번 - 요세푸스 문제 (Silver 4)

문제 링크

[백준] 1158번 - 요세푸스 문제 (Silver 4)

문제 설명

(N, K)-요세푸스 순열을 출력한다.

1. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있을 때 K번째 사람을 제거한다.
2. 남은 사람들로 이루어진 원에서 K번째 사람을 제거한다.
3. 모든 사람이 제거될 때까지 반복한다.

위 과정에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다.

정답 코드 및 설명

자료구조 큐를 이용해서 구현할 수 있다.
큐는 FIFO(First Input First Out) 자료구조이다.
맨 앞의 사람을 제거해서 다시 넣어주는 것을 K번 반복하면 K번째 사람이 맨 앞에 오게 된다.
K번째 사람을 제거할 때는 위의 과정을 수행했을 때 맨 앞에 있는 사람을 제거하면 된다.

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ1158 {
    int n, k;
    Queue<Integer> people = new LinkedList<>();
    int[] seq;

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        for (int i = 0; i < n; i++)
            people.add(i + 1);
        seq = new int[n];
    }

    void makeSequence() {
        int index = 0;
        while (index < n) {
            for (int i = 1; i < k; i++)
                people.add(people.poll());
            seq[index++] = people.poll();
        }
    }

    void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        sb.append('<');
        for (int i = 0; i < n; i++) {
            sb.append(seq[i]);
            if (i != n - 1) sb.append(", ");
        }
        sb.append('>');
        bw.write(sb.toString());
        bw.close();
    }

    void solution() throws IOException {
        input();
        makeSequence();
        print();
    }

    public static void main(String[] args) throws IOException {
        new BOJ1158().solution();
    }
}