[Java] 요제푸스 문제: 인덱스 계산 없이 '큐 회전'으로 해결하기

“한 줄 요약: Queue의 회전(Rotation) 원리를 이용해 원형 구조의 인덱스 계산 없이 요제푸스 순열 추출”

1. 🔍 문제 분석 (Problem Understanding)

• 핵심 제약 조건: $N$명의 사람이 원형으로 앉아 있고, K번째 사람을 반복적으로 제거한다.(1 ≤ K ≤ N ≤ 1,000)
• 요구 사항: 제거되는 순서대로 숫자를 나열한 ‘요제푸스 순열’을 <n1, n2, ...> 형태로 출력.
• 나의 첫 생각: 처음에는 큐의 front 포인터를 직접 움직이면서 데이터를 찾으려 했다. 그런데 원형 구조라 끝에 도달했을 때 다시 처음으로 되돌리는 로직을 짜는 게 생각보다 복잡하고 꼬였다.

---

2. 💡 해결 전략 (Approach)

• 사용된 자료구조/알고리즘: ArrayDeque (Queue), ArrayList (결과 저장용), Stream API (출력 처리).
• 로직 설계:
  1. 1부터 N까지 큐에 순차적으로 삽입.
  2. 큐가 빌 때까지 다음을 반복:
     • 회전: K-1번까지 queue.poll()로 맨 앞의 사람을 꺼내고, queue.offer()로 다시 맨 뒤로 보낸다. (데이터를 옮겨 기준점을 유지하는 방식!)
     • 추출: K번째 사람은 poll()만 수행하고 다시 넣지 않은 채 removedNumbers 리스트에 저장해준다.
  3. 모든 데이터가 추출되면 리스트를 스트림으로 변환해 형식을 맞춰 출력해준다.

3. 🚧 삽질 기록 (Troubleshooting)

• 문제 발생: 3번째 순회부터 front 위치 세팅이 꼬였다. 출력 시 큐 객체를 직접 스트림으로 돌리려니 데이터 소모와 출력이 섞여 순서 보장이 어렵다.
• 원인 분석: 큐는 데이터를 소모하며 진행되는 구조라 순회와 소모를 동시에 하려다 기준점이 모호해진다. 또한 joining은 문자열에만 동작하는데 Integer를 그대로 사용하려 했다.
• 해결 방법: “지나치는 값은 뒤로 보내고, 제거할 값은 꺼낸다”는 단순한 회전 로직으로 전환하고 결과는 별도 List에 담은 뒤, map(String::valueOf)로 변환하여 joining 적용했다.

---

4. ✅ 최종 코드 (Final Code)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;

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());
        
        // LinkedList보다 연속된 메모리 구조로 성능이 좋은 ArrayDeque 사용
        Queue<Integer> queue = new ArrayDeque<>();

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        for (int i = 1; i <= N; i++) {
            queue.add(i);
        }

        List<Integer> removedNumbers = new ArrayList<>();

        while (!queue.isEmpty()) {
            // K-1번째까지는 다시 뒤로 보냄 (회전 시뮬레이션)
            for (int i = 0; i < K - 1; i++) {
                queue.offer(queue.poll());
            }
            // K번째 대상자는 완전히 제거 후 리스트에 저장
            removedNumbers.add(queue.poll());
        }

        // Collectors.joining(구분자, 접두사, 접미사) 오버로딩 활용
        String result = removedNumbers.stream()
                .map(String::valueOf)
                .collect(Collectors.joining(", ", "<", ">"));

        System.out.println(result);
    }
}

---

5. 📝 배운 점 (Key Takeaways)

기술적 수확: ArrayDeque는 인덱스 접근이 빠르고 가비지 컬렉션 부담이 적어 큐 구현에 최적임을 배웠고 Collectors.joining(", ", "<", ">")를 사용하면 접두사와 접미사까지 한 번에 처리할 수 있어 코드가 선언적으로 변했다.

반성: “원형”이라는 단어에 갇혀서 포인터 조작만 고집했고 자료구조의 특성을 이용해 문제를 ‘단순화’하는 시야가 중요함을 느꼈다. 앞으로 알고리즘 공부를 하면서 이런 시야를 더 넓혀야겠다고 생각했다.