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

문제 해석

• 1번부터 N번 까지의 사람들이 원을 이루며 있는데, 그 N명의 사람 중 K번째를 제거하는 작업을 사라질 때까지 반복한다.(K번째를 삭제 후 K+1번이 1번이 된다. => 원형이니까)
• 그냥 글로 설명하면 무슨 말인지 모를 수 있다. 그림으로 문제를 해석하면 아래와 같다.
  

코드

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static Queue<Integer> queue = new LinkedList<>();// 정수를 저장하는 큐

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st =new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); // N : 사람 수
        int K = Integer.parseInt(st.nextToken()); //K : 제거해야하는 인덱스(사람 순서)

        br.close();

        for(int i = 1; i <= N; i++){ //1~N번까지의 사람
            queue.add(i);
        }

        sb.append("<"); //여는 괄호

        while(queue.size() > 1){ //마지막 숫자는 ',' 없어서 size가 1까지만 반복

            // 큐 기준 0번째 인덱스부터 K-1까지는 뒤로 추가 한다. (해당 큐 맨 뒤에 값 삽입)

            for(int i = 0; i < K - 1; i++) {
                //일단 앞에 있는 요소를 삭제하여 반환값으로 나온 값을 다시 뒤에 추가하는 방식
                /*
                 예) K = 3
                 1 2 3 4 5 6
                 3 4 5 6 1 2이 방식으로 진행한다.
                */
                queue.offer(queue.poll());
            }
            //그리고 K번째가 가장 앞으로 왔으니 삭제해준다
            // poll() : 가장 앞에 있는 요소를 제거한다.
            sb.append(queue.poll()).append(", ");
        }

        //마지막 요소는 괄호가 마지막에 없으로 따로 빼준다.
        sb.append(queue.poll()).append(">"); //닫는 괄호

        System.out.println(sb);
    }
}

• 코드에 대한 설명은 주석으로 작성해두었다.

결과

느낀 점

• 큐 구현 클래스 사용하면 너무 쉽게 풀리는 문제인데 처음에 기본 배열로 수행하려다가 애 좀 먹고 해결 법을 못찾아 제공하는 클래스 사용했다. (클래스한테 져버렸다...)