백준 11866: 요세푸스 문제 0(java)

문제

---

풀이

 

큐의 전단과 후단에서 삽입과 삭제가 모두 일어나므로, 마찬가지로 덱을 사용해 풀이했다. 

for(int i=0; i<N; i++) {
	deque.addLast(i+1);
}

우선 1부터 N까지의 값을 덱에 삽입하여 덱을 완성한다. 

이제 K번째 요소를 덱에서 제거해야 하지만, 스택이나 큐와 마찬가지로 덱에서도 인덱스를 사용하여 덱의 중간에 삽입하거나 삭제할 수 없다. 따라서 K번째 값을 제거할 수 있도록 해당 요소를 덱의 전단이나 후단으로 이동시키는 연산이 필요하다.

for(int i=0; i<K-1; i++) {
	deque.addLast(deque.removeFirst());
}

K번째 요소를 전단으로 가져오려면 K 앞에 있는 K-1개의 요소들을 제거한 뒤 후단에 삽입해야 하므로 위와 같이 작성할 수 있다. 도식적으로 표현하면 아래와 같다.

사람들이 모두 제거될 때까지 위 과정을 반복해주면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
		Deque<Integer> deque=new LinkedList<>();
		StringBuilder sb=new StringBuilder();
		
		StringTokenizer st=new StringTokenizer(in.readLine());
		int N=Integer.parseInt(st.nextToken());
		int K=Integer.parseInt(st.nextToken());
		int[] arr=new int[N];
		
		for(int i=0; i<N; i++) {
			deque.addLast(i+1);
		}
		
		while(true) {
			if(deque.size()==1) {
				System.out.println("<"+sb+deque.remove()+">");
				break;
			}
			
			for(int i=0; i<K-1; i++) {
				deque.addLast(deque.removeFirst());
			}
			sb.append(deque.removeFirst()+", ");
		}
	}
}

StringBuilder를 사용해 값을 모두 모았다가 한 번에 출력했다.