[Java/백준/Queue(큐)] 1158번: 요세푸스 문제, 11866번: 요세푸스 문제 0

문제

www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

 

www.acmicpc.net/problem/11866

11866번: 요세푸스 문제 0

 

 

두 문제는 범위만 다른 동일한 문제이다.

위 문제는 자료구조 중 Queue를 사용하면 쉽게 풀 수 있다.

 

큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 FIFO(선입선출) 구조를 띄고 있다.

 

예제의 7 3을 예로 들면

처음엔 <1, 2, 3, 4, 5, 6, 7> 에서

1을 빼서 7 뒤로 넣고,

2를 빼서 7 뒤의 1 뒤에 넣고,

3을 삭제한다.

그 뒤, 4를 빼서 뒤에 넣고,

5를 빼서 뒤로 넣고,

6을 삭제한다.

의 과정을 반복해주면 된다.

 

package boj;

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

public class BOJ1158 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] info = br.readLine().split("\\s");
		int n = Integer.parseInt(info[0]);
		int k = Integer.parseInt(info[1]);
		StringBuilder sb = new StringBuilder();
		Queue<Integer> queue = new LinkedList<Integer>();
		
		for(int i=1; i<n+1; i++) {
			queue.offer(i);
		}
		
		sb.append("<");
		while(!queue.isEmpty()) {
			for(int i=0; i< k-1; i++) {
				queue.offer(queue.poll());
			}
			sb.append(queue.poll());
			if(queue.size()==0)
				sb.append(">");
			else
				sb.append(", ");
		}
		System.out.println(sb);
		br.close();
	}
	
}