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

문제설명

 

 

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		Queue<Integer> tmp = new LinkedList<>();
		Queue<Integer> ans = new LinkedList<>();
		for(int i = 1; i <= N; ++i) tmp.add(i);
		while(!tmp.isEmpty())
		{
			for(int i = 1; i < K; ++i) tmp.add(tmp.poll());
			ans.add(tmp.poll());
		}
		System.out.print("<");
		while(ans.size() > 1)System.out.print(ans.poll() + ", ");
		System.out.print(ans.poll() + ">");
	}
}

 

설명

핵심 코드는 아래의 코드이다.

for(int i = 1; i < K; ++i) tmp.add(tmp.poll());
ans.add(tmp.poll());

만약 K = 3이라면 1 2 3 4 5 6 7 중에서 맨 앞 두 개를 잘라내기 후 붙여넣는다. -> 3 4 5 6 7 1 2

이후 맨 앞의 3을 ans큐에 넣는다.

이 행동을 tmp 큐가 비워질 때 까지 반복한다.

tmp	1 2 3 4 5 6 7	ans	null
	4 5 6 7 1 2		3
	7 1 2 4 5		3 6
	4 5 7 1		3 6 2
	1 4 5		3 6 2 7
	1 4		3 6 2 7 5
	1		3 6 2 7 5 1
	null		3 6 2 7 5 1 4

 

그 다음 ans 큐의 모든 원소를 출력하면 된다.