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

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

1158번: 요세푸스 문제

 

• 풀이

큐를 이용하는 문제이다.

poll한 숫자를 다시 offer(add)해줌으로써 원순열을 구현할 수 있다.

큐가 빌 때까지 while문을 돌리고, K번째 숫자가 나올 때까지 poll한 숫자를 다시 add한다. K번째 숫자는 제거한다.

 

• 코드

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

public class Main {
	public static void main(String [] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		// 큐 생성
		Queue<Integer> que = new ArrayDeque<>();
		for (int i=1; i<=N; i++) que.add(i);
		
		// 결과 출력용 StringBuilder
		StringBuilder result = new StringBuilder();
		result.append("<");
		
		while(!que.isEmpty()) {
			for (int i = 0; i<K-1; i++) {
				que.add(que.poll());
			}
			result.append(que.poll());
			if (que.size()!=0) result.append(", "); // 마지막 값이 아닐 경우에만 추가
		}
		
		result.append(">");
		System.out.println(result);
	}
}