[백준 - 1158] 조세퍼스 문제

조세퍼스 문제

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	7360	3632	2855	51.881%

문제

조세퍼스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 M(≤ N)이 주어진다. 이제 순서대로 M번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, M)-조세퍼스 순열이라고 한다. 예를 들어 (7, 3)-조세퍼스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 M이 주어지면 (N,M)-조세퍼스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ M ≤ N ≤ 5,000)

---

ㅇ

---

갱장히 쉬울꺼 같은 조세퍼스 문제

저번에 우선순위 큐가 나온 김에 하나 풀어보자고 고름

2+1 개념 ㅎ

package beak.josephus_1158;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by eunbi on 2018-01-04.
 *
 * 7, 3 -> <3, 6, 2, 7, 5, 1, 4>
 */
public class Josephus_eunbi  {
    public static Queue queue = new LinkedList();
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception{

        java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
        String readLine = br.readLine();
        String[] spl = readLine.split(" ");
        int N = Integer.parseInt(spl[0]);
        int M = Integer.parseInt(spl[1]);

        insert(N);
        josephus(M);

        System.out.println("<"+sb.substring(0, sb.length() - 2)+">");

    }
    public static void josephus(int num){
        int index=0;
        int value ;
        while(queue.size()>0){
            index = index % num;
            index++;
            value = Integer.parseInt(queue.poll().toString());
            if(index == num){
                sb.append(value).append(", ");
            }else{
                queue.offer(value);
            }

        }
    }
    public static void insert(int n){
        for(int i=1;i<=n;i++){
            queue.offer(i);
        }
    }



}