[백준] 11866번 요세푸스 문제 0 (JAVA)

문제

- 1 ~ N번의 N명의 사람이 원을 이루며 앉아있고, 양의 정수 K(<=N)가 주어짐

- 순서대로 K번째 사람을 제거

- 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나감

- N명의 사람이 모두 제거될 때까지 계속됨

 

해결방법

1부터 N까지의 수를 큐에 담아서 문제를 해결하였다. 큐에 담게 되면 N번째 사람을 제거하려고 할 때, 앞에 있던 사람들을 큐의 뒷부분에 다시 넣어주고 N번째 사람을 StringBuilder에 쌓아서 요세푸스 순열을 출력할 수 있도록 하였다.

 

코드

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

public class Main {
    static int N, K;
    static Queue<Integer> queue;
    static StringBuilder sb;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();

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

	// 순열을 담을 큐
        queue = new ArrayDeque<>();

	// 차례로 숫자를 큐에 담음
        for(int i = 1; i<=N; i++){
            queue.add(i);
        }

	// 출력 양식을 맞추기 위해 StringBuilder에 추가
        sb.append("<");

	// 요세푸스 순열 구하기
        solution();
		
        // 추가된 ", "를 제거하고 출력 양식을 맞추기 위해 ">"를 StringBuilder에 추가
        sb.delete(sb.length()-2, sb.length()).append(">");
		
        // sb에 쌓아놓은 내용 출력
        System.out.println(sb);
    }

    static void solution(){
    	// 큐가 비어있지 않을 동안
        while (!queue.isEmpty()){
            // K번째 이전의 숫자들을 큐의 뒤로 이동시킴
            for(int i = 0; i<K-1; i++){
                queue.add(queue.poll());
            }
            // K번째의 숫자는 꺼내어 StringBuilder에 추가
            sb.append(queue.poll()+", ");
        }
    }
}