요세푸스 문제

import java.util.Scanner;

public class Main {

  private static class Queue {
      private int[] queue;
      private int front, rear, size, capacity;

      public Queue(int capacity) {
          this.capacity = capacity;
          this.queue = new int[capacity];
          this.front = 0;
          this.rear = -1;
          this.size = 0;
      }

      public void enqueue(int x) {
          if (size == capacity) {
              throw new IllegalStateException("full");
          }
          rear = (rear + 1) % capacity;
          queue[rear] = x;
          size++;
      }

      public int dequeue() {
          if (size == 0) {
              throw new IllegalStateException("Queue is empty");
          }
          int result = queue[front];
          front = (front + 1) % capacity;
          size--;
          return result;
      }

      public int peek() {
          if (size == 0) {
              throw new IllegalStateException("empty");
          }
          return queue[front];
      }

      public boolean isEmpty() {
          return size == 0;
      }
  }

  public static void main(String[] args) {
      Scanner sc = new java.util.Scanner(System.in);
      int N = sc.nextInt();
      int K = sc.nextInt();
      sc.close();

      Queue queue = new Queue(N);
      

      for (int i = 1; i <= N; i++) {
          queue.enqueue(i);
      }
      
      StringBuilder result = new StringBuilder();
      result.append("<");
      
      while (!queue.isEmpty()) {

          for (int i = 1; i < K; i++) {
              queue.enqueue(queue.dequeue());
          }

          result.append(queue.dequeue());
          if (!queue.isEmpty()) {
              result.append(", ");
          }
      }
      
      result.append(">");
      System.out.println(result);
  }
}

요세푸스 문제(Josephus Problem)**는 원형 큐(또는 원형 리스트)에서 K번째 사람을 계속 제거하여 마지막 한 명이 남을 때까지 반복하는 문제입니다.

✔ 문제 설명

1. N명의 사람이 원형으로 앉아 있음
2. 1번부터 N번까지 차례로 번호가 부여됨
3. K번째 사람을 제거하고, 그다음 K번째 사람을 계속 제거함
4. 모든 사람이 제거될 때까지 반복
5. 제거된 순서를 출력

✔ 원형 큐의 특징

• enqueue() → 요소를 큐의 끝에 추가
• dequeue() → 큐의 맨 앞 요소를 제거
• peek() → 현재 맨 앞 요소 확인
• 순환 구조: rear와 front가 capacity를 넘어서면 다시 0으로 돌아감

✔ 큐의 동작

• K-1번 요소를 앞에서 빼고 다시 넣음 → 순서를 유지
• K번째 요소를 제거
• 반복하여 모든 요소 제거 후 출력

링크드리스트 방식

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class JosephusLinkedList {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        sc.close();

        List<Integer> list = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            list.add(i);
        }

        StringBuilder result = new StringBuilder();
        result.append("<");

        int index = 0;
        while (!list.isEmpty()) {
            index = (index + K - 1) % list.size(); // 원형 구조 유지
            result.append(list.remove(index));
            if (!list.isEmpty()) {
                result.append(", ");
            }
        }

        result.append(">");
        System.out.println(result);
    }
}