[문제풀이] B1158 요세푸스 문제

요세푸스 문제

---

  🪅 일부가 순환되는 것을 보며 큐(queue)를 생각할 수 있느냐
  🪅 큐를 구현할 수 있느냐

💡 문제 접근 과정
: k번째가 되어 제거되기 전까지는 첫번째 ~ k-1번째까지는 순서가 뒤로 밀린다.
즉, 첫번째부터 k-1번째까지 빼서 뒤로 넣으면 되고, 빼는 출구와 넣는 입구가 다르므로 큐를 생각해냈다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

/*
 * 백준 1158번 요세푸스 문제
 * 
 * 입력:
 * 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)
 * 
 * 출력:
 * 예제와 같이 요세푸스 순열을 출력한다.
 * 
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(bf.readLine(), " ");
        int N = Integer.parseInt(token.nextToken()); // 7
        int K = Integer.parseInt(token.nextToken()); // 3번째

        // queue, 1 2 3 4 5 6 7
        Queue<Integer> queue = new ArrayDeque<>();
        for(int i = 1; i <= N; i++) {
            queue.add(i);
        }
        StringBuilder builder = new StringBuilder();

        builder.append("<");
        int startIdx = 0;
        int removeIdx = K-1;
        //7번을 제거하는 과정을 반복
        for(int i = 0; i < N; i++) { // 7번
            // k번째 수 제거하는 과정

            // K-1번째까지 앞에서 빼고 뒤로 넣기
            for(int j = startIdx; j < removeIdx; j++) { // 0, 1
                int current = queue.remove();
                queue.offer(current);
            }
            // K번째 수 제거
            int result = queue.remove();
            if(i == N-1) {
                builder.append(result + ">");
                break;
            }
            builder.append(result+", ");
        }

        System.out.println(builder.toString());
    }
}