[백준] 11866번 - 원형 큐(Queue)

>>문제 바로가기<<

요세푸스 순열을 출력하는 문제이다.

처음에 시도한 방식은 포인터 역할을 하는 변수를 하나 만들어서, 그 변수가 가리키는 데이터를 지우도록 시도했다.

하지만 그러면 포인터를 관리하기가 복잡해지므로
차라리 원형 큐 방식을 사용하는 쓰는게 더 간편하다.

---

Queue<Integer> q = new LinkedList<>();

while(q.isEmpty()){
	for(int i=0; i<K-1; i++){
    	q.add(q.poll());
        // 원소를 빼내는 작업과 집어넣는 작업이 동시에 일어난다.
    }
    
    q.poll();
    ...
}

매 시행마다
큐의 0번째 원소부터 K-1번째 원소를 K번째 원소 뒤로 옮기는 과정이다.
그럼 다음에 빠지는 데이터는 우리가 원하는 데이터는 K번째 원소가 된다.

위 정보를 바탕으로 설계한 코드는 다음과 같다.

---

import java.util.*;

class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int K = sc.nextInt();
        Queue<Integer> q = new LinkedList<>();
        
        for(int i=1; i<=N; i++){
        	q.add(i);
        }
        
        System.out.print("<");
        
        while(!q.isEmpty()){
        	for(int i=0; i<K-1; i++){
            	q.add(q.poll());
            }
            
            System.out.print(q.poll());
            
            if(!q.isEmpty()){
            	System.out.print(", ");
            }
       	}
        
        System.out.print(">");
    }

}

맞았습니다!!