[알고리즘/백준] 11866번 : 요세푸스 문제 0(Java)

문제	11866번 : 요세푸스 문제 0
문제링크	https://www.acmicpc.net/problem/11866
난이도	S4
언어	Java
분류	구현, 자료구조, 큐

 

 

📌 최종 정답 코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 입력 파싱 (한 줄에 N과 K가 주어짐)
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 사람 수
        int K = Integer.parseInt(st.nextToken()); // 제거할 순번

        // 1부터 N까지 큐에 넣기
        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) {
            // 앞에서 K-1개를 뒤로 보냄
            for (int i = 0; i < K - 1; i++) {
                queue.offer(queue.poll());
            }
            // K번째 사람 제거
            sb.append(queue.poll()).append(", ");
        }

        // 마지막 남은 사람 추가 (콤마 없이)
        sb.append(queue.poll()).append(">");

        // 결과 출력
        bw.write(sb.toString());
        bw.newLine();

        // 스트림 닫기
        br.close();
        bw.flush();
        bw.close();
    }
}

📌 구해야 하는 정답

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

📌 코드 설계하기