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

• 백준URL
  

---

문제 접근

1. 1부터 N까지의 사람을 Deque에 넣는다.
2. K번째 사람을 제거해야 하므로,
   • K-1번 동안 큐의 맨 앞 원소를 맨 뒤로 보낸다 (pollFirst → offerLast).
3. K번째 사람이 Deque의 맨 앞으로 오면, 제거 후 출력에 추가한다.
4. Deque가 빌 때까지 이를 반복한다.

즉, 하나의 사이클을 다음과 같이 수행한다:

앞에서 꺼내서 뒤로 K-1번 이동 → K번째 사람 출력(제거)

---

Deque 자료구조 사용 이유

이 문제는 원형 회전 구조를 시뮬레이션해야 한다.
Queue로도 구현 가능하지만, 맨 앞 요소를 빼고 뒤로 보낼 때
양방향 입출력 기능이 있는 Deque (ArrayDeque) 를 사용하면 훨씬 간단하게 구현할 수 있다.

사용된 주요 메서드:

• removeFirst() : 맨 앞 요소 꺼내기
• addLast() : 꺼낸 요소를 맨 뒤에 삽입
  이 두 연산을 반복하며 원형 구조를 그대로 시뮬레이션한다.

---

시뮬레이션 예시

예를 들어 N = 7, K = 3인 경우의 실행 과정:

단계	Deque 상태	꺼내서 뒤로 이동	출력 결과
초기		-	<
1		1, 2 → 뒤로	<3
2		4, 5 → 뒤로	<3, 6
3		7, 1 → 뒤로	<3, 6, 2
4		4, 5 → 뒤로	<3, 6, 2, 7
5		1, 7 → 뒤로	<3, 6, 2, 7, 5
6		7 → 뒤로	<3, 6, 2, 7, 5, 1
7	[]	-	<3, 6, 2, 7, 5, 1, 4>

---

정리

• Deque(ArrayDeque) 을 사용하면 원형 큐의 회전 로직을 쉽게 구현할 수 있다.
• K-1번의 회전 후 pollFirst()를 하면 K번째 사람이 제거된다.
• StringBuilder를 이용해 출력 형식을 효율적으로 구성한다.
• 최종 시간 복잡도는 O(N × K) 이지만 N ≤ 1000 범위 내에서는 충분히 효율적이다.

---

제출

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

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());

        Deque<Integer> dq = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) dq.add(i);

        StringBuilder result = new StringBuilder("<");

        while (!dq.isEmpty()) {
            for (int i = 0; i < k - 1; i++) {
                dq.addLast(dq.removeFirst());
            }
            result.append(dq.removeFirst());
            if (!dq.isEmpty()) result.append(", ");
        }

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