[백준] 11866 요세푸스 문제 0 - Java

📌 문제 정보

• 출처: 문제 링크
• 난이도: ⭐
• 문제 유형: STACK / QUEUE
• 사용 언어: Java

---

🔍 문제 설명

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

---

💡 풀이 노트

while (!q.isEmpty()) {
    for (int i = 0; i < K - 1; i++) {
        q.offer(q.poll());  // 앞에서 꺼내서 뒤로 넣기
    }
    arr[idx++] = q.poll();  // K번째 사람 제거
}

 

• 1부터 N까지 큐에 넣는다.
• 매 턴마다:
  • `K-1`번 `poll()`하여 큐의 앞 사람들을 다시 뒤로 보냄 → 회전
  • `K번째 사람은 제거(poll)` → 제거 순서 배열에 저장
• 큐가 빌 때까지 반복

---

🚀 코드 (Java)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws 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);
        }

        int[] arr = new int[N];
        int idx = 0;

        while (!q.isEmpty()) {
            for (int i = 0; i < K - 1; i++) {
                q.offer(q.poll());
            }
            arr[idx++] = q.poll();
        }

        System.out.print("<");
        for (int i = 0; i < N; i++) {
            if (i != N - 1) {
                System.out.print(arr[i] + ", ");
            } else {
                System.out.print(arr[i]);
            }
        }
        System.out.print(">");
    }
}

---

🖥 실행 결과

입력

7 3

 

출력

<3, 6, 2, 7, 5, 1, 4>

 

---

🔄 개선 가능성

• `Deque`를 사용하면 양방향 회전이 필요한 경우 더 확장된 구현이 가능함

📌 깃허브 코드 저장소: https://github.com/glorypang/CodingTest