[백준] 1158번 요세푸스 문제 [JAVA]

https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

---

     문제

     문제 풀이

• 전형적인 큐 문제이다.
• 순서대로 k번째 사람에 접근해야되는데, 큐 문제가 될 수 있는 이유는 Circular queue를 생각하면 된다. 원을 이루고 있기 때문에, 1번째부터 k-1번째 사람을 순서대로 뒤로 붙여, 순서를 뒤로 미루는 방식으로 접근하면 된다. k번째 사람이 1번째 순서가 될 때까지 앞의 사람들을 다 뒤로 보내고 k번째 사람이 1번째 순서가 되면 해당 사람을 빼버리면 된다.
• 푼 방법
  1. 큐를 두 개 만든다.(qu, qu2)
  2. 1부터 N까지 순서대로 qu에 넣는다.(front = 1, back = N)
  3. for문을 통해 K-1번째 사람까진 다시 qu.add(qu.poll())을 반복한다.
  4. 해당 for문에서 K번째 사람까지 도달하게 되면 그 값은 qu2로 add시켜준다.(qu2.add(qu.poll))
  5. 위의 for문을 N번 반복하게 되면, qu에 들어있는 모든 멤버를 검토할 수 있다.

---

        JAVA code

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

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

        int[] input = new int[2];
        int x = 0;
        while (st.hasMoreTokens()) {
            input[x] = Integer.parseInt(st.nextToken());
            x++;
        }

        Queue<Integer> qu = new LinkedList<>();
        Queue<Integer> qu2 = new LinkedList<>();
        for (int i = 1; i <= input[0]; i++)
            qu.add(i);
        // 1 , 2 빼고 뒤로 추가 , 3은 빼고 다른 qu 에 삽입
        for (int i = 0; i < input[0]; i++) {
            for (int j = 0; j < input[1]; j++) {
                if (j == (input[1] - 1)) {
                    qu2.add(qu.poll());
                } else {
                    qu.add(qu.poll());
                }
            }
        }
        System.out.print("<");
        for (int i = 0; i < input[0]; i++) {
            if (i == (input[0] - 1)) {
                System.out.println(qu2.poll() + ">");
            } else
                System.out.print(qu2.poll() + ", ");
        }
    }
}