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

11866번: 요세푸스 문제 0 (acmicpc.net)

11866번: 요세푸스 문제 0

 

 

풀이 과정 

 

- k-1번째 까지 요소를 디큐 

- 디큐한 요소들을 인큐 

- k번째 요소를 디큐 

- 위의 과정을 큐의 사이즈가 1보다 클 때까지 반복 

- 마지막으로 남은 요소를 디큐하여 출력

 

 

요세 푸스 문제 

요세푸스와 순열_살아남은 자의 수학 공식 : 네이버 블로그 (naver.com)

요세푸스와 순열_살아남은 자의 수학 공식

 

Java: 큐(Queue)의 개념과 사용법, 요세푸스 순열 : 네이버 블로그 (naver.com)

Java: 큐(Queue)의 개념과 사용법, 요세푸스 순열

 

- n과 k가 자연수이고, k<n이라고 가정

  - n명이 동그랗게 모여 있을 때 임의의 한 명부터 순서를 세어 k번째 사람을 모임에서 제외 

  - 남은 n-1명에서 다시 순서를 세어 k번째 사람을 제외 

 

- 이 과정을 아무도 남지 않을 때까지 계속 반복

- 이때 모임에서 제외되는 사람의 순서를 (n,k) 요세푸스 순열이라고 함 

 

 

ex) (7,3)- 요세푸스 순열 <3,6,2,7,5,1,4>

 

 

 

 

정답

 

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

public class Main {
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        Queue<Integer> queue = new LinkedList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        for(int i=1; i<=n; i++)
        {
            queue.add(i);
        }
        
        bw.write("<");
        
        while(queue.size()>1)
        {
            for(int i=0; i<k-1; i++)
            {
                int temp = queue.poll();
                queue.add(temp);
            }
            
            bw.write(queue.poll()+"");
            bw.write(", ");
        }
        
        bw.write(queue.poll()+"");
        bw.write(">");
        
        
        bw.flush();
        bw.close();
        
    }
}