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

문제

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

1158번: 요세푸스 문제

---

코드(JAVA)

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

public class Main {

	public static void main(String[] args) throws IOException {
		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> queue = new ArrayDeque<>();
		
		for(int i =1 ; i <= n ; i++) {
			queue.offer(i);
		}
		int cnt = 1;
		int idx = 0;
		int[] josephus = new int[n]; 
		while(!queue.isEmpty()) {
			if(cnt++%k == 0) {
				josephus[idx++] = queue.poll();
			}
			else {
				queue.offer(queue.poll());
			}
		}
		System.out.println(Arrays.toString(josephus).replace("[", "<").replace("]", ">"));
	}

}

---

풀이

원형모양으로 앉아 있다는 것때문에 처음에는 LinkedList를 생각했으나, 이번문제는 Queue로 간단하게 해결할 수 있는 문제!

 

우선 큐에 1~n까지의 값을 넣어준다.

그 후, 큐가 빌 때까지(사람이 남지 않을 때 까지) while문을 돌리며 

cnt%3 == 0 이면 poll로 큐에서 값을 빼고 바로 josephus배열에 넣는다.

그렇지 않다면, poll한 값을 다시 offer하여 원형 구조를 만들어 준다.

 

출력은 Arrays의 toString 출력에서 [] 모양만 바꿔주면 되므로 그냥 System.out.println으로 바로 출력 해주었다.