159. 11866(요세푸스 문제 0) - 자바

import java.util.*;
import java.io.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		int N = sc.nextInt();
		int K = sc.nextInt();
		Deque<Integer> queue = new ArrayDeque<>();

		for (int i = 1; i <= N; i++) {
			queue.add(i);
		}
		sb.append("<");
		while (!queue.isEmpty()) {
			for (int i = 0; i < K - 1; i++) {
				queue.add(queue.poll());
			}
			if(queue.size()==1) sb.append(queue.poll()).append(">");
			else sb.append(queue.poll()).append(", ");			
		}
		
		System.out.println(sb);

	}
}

문제요약

요세푸스 순열을 완성하시오.

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=attractorlim&logNo=221030930874 

요세푸스문제 Josephus problem 순열

설명

간단히 반복적으로 K번째를 제거하라는 말이다.

큐를 이용해 K번째를 제거하기 위해서는 K번째 보다 앞에있는 것은 뒤로 보내준다.

입력이

다음과 같을때,

다음과 같이 값을 구할 수 있다.

 

설명을 하면, 큐를 이용했을 때 큐 안에 값이 없을 때 까지 K-1번 앞에 있는 값을 뒤로 보내고, K번째 되었을 때 값을 꺼내

다른 곳에 저장한다.

 

		Deque<Integer> queue = new ArrayDeque<>();

		for (int i = 1; i <= N; i++) {
			queue.add(i);
		}

값을 1부터 N까지 저장한다.

		sb.append("<");
		while (!queue.isEmpty()) {
			for (int i = 0; i < K - 1; i++) {
				queue.add(queue.poll());
			}
			if(queue.size()==1) sb.append(queue.poll()).append(">");
			else sb.append(queue.poll()).append(", ");			
		}

		sb.append("<");

나중에 출력형식에 맞춰주기 위해 <를 미리 넣어줌

while (!queue.isEmpty())

큐 내에 값이 없을 때 까지 반복한다.

			for (int i = 0; i < K - 1; i++) {
				queue.add(queue.poll());
			}

K-1번 앞에 있는 값을 뒤로 보내는 행위를 반복한다.

			if(queue.size()==1) sb.append(queue.poll()).append(">");
			else sb.append(queue.poll()).append(", ");

 

 

값을 꺼냄과 동시에 sb에 저장한다.

만약, 큐사이즈가 1이라면 끝자리를 의미하므로 ">"를 그려주고 아니라면

값과 함께 ", "을 그려준다.