BOJ 1157. 요세푸스 문제

BOJ 1158. 요세푸스 문제

풀이

큐를 이용하여 요세푸스 순열을 만든다.
먼저 입력으로 N=7이 들어왔을 때 초기 상태로 1부터 7까지 큐에 넣는다.

그 다음  K=3이므로 3번째 사람을 제거해야 하므로
큐에서 순서대로 poll() 한 뒤 다시 offer()로 큐에 넣어준다.

그리고 3번째가 되었을 때 poll() 한뒤 다시 큐에 넣지 않고 출력 버퍼에 저장한다.

다시 반복하여 2번 poll(), offer()

3번째가 되었을 때 또다시 큐에 넣지 않고 출력 버퍼에 저장

계속 반복하여 순열을 완성한다.

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.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 sb = new StringBuilder();

        sb.append("<");
        while (queue.size() > 1) {
            for (int j = 1; j < k; j++) {
                queue.offer(queue.poll());
            }

            sb.append(queue.poll()).append(", ");
        }
        sb.append(queue.poll()).append(">");
        System.out.print(sb);
    }
}

import java.util.*

fun main () {
    val scanner = Scanner(System.`in`)
    val n = scanner.nextInt()
    val k = scanner.nextInt()

    val queue = LinkedList((1..n).toMutableList())

    print("<")
    while (queue.size > 1) {
        repeat((1 until k).count()) { queue.add(queue.pop()) }
        print("${queue.pop()}, ")
    }
    print("${queue.remove()}>")
}

풀이소스

github.com/beomjo/algorithm-study/blob/main/BOJ/java/1158.java github.com/beomjo/algorithm-study/blob/main/BOJ/kotlin/1158.kt