자료구조[queue]_백준_11866

s

출력형식만 맞춰주고, 큐를 이해하고 있다면 기본적인 개념으로 간단하게 풀이할 수 있는 문제입니다. 

[문제 분석]

• 환형큐에 대한 문제가 나왔습니다. 
• 환형 큐 또한 기본 큐를 기준으로 만든것이기 때문에 값을 넣고 빼는 메커니즘은 동일합니다. 
• 환형큐 내부가 요소로 가득찬 경우, front에 있는 값을 poll or remove하면 front의 위치가 한 칸 이동하기 때문에, 새로운 값을 offer or add할 때 rear의 위치가 기존에 front가 있던 위치로 이동하게 됩니다. 원활한 이해를 통해 그림을 보겠습니다. 

• 그렇다면 원으로 둘러쌓인(환형큐) 사람들을 탐색하면서 K번째 사람들을 연쇄적으로 배출할겁니다.
• 이때, 큐의 요소를 중간부터 삭제하고자 하는 것은 기본적인 큐에대한 이해가 부족한 것입니다. 
• 물론 LinkedList를 사용하면 중간에서 삭제하고 끊어진 부분을 다시 이어가고 할 수 있겠지만 이 문제를 풀기 위해서 필요이상으로 복잡하다고 생각하여 필자는 다른 방식으로 풀었습니다.  

맨 왼쪽을 기준으로 K번째 요소를 삭제해야 합니다. 기본적으로 큐에서는 front에 있는 요소를 삭제할 수 있습니다.     따라서 K-1번째까지의 요소들을 모두 poll한 다음 큐의 rear부분에 다시 offer를 해줄겁니다. 그렇게 한다면 K번째 요소가 front의 위치로 오면서 삭제할 준비가 되었습니다.  기본 큐를 사용하여 환형 큐의 구조로 적용한 것입니다. 

그림을 보시면 이해가 될것입니다.  처음으로 K 번째 요소를 제거하면 다음과 같습니다. 

기본 로직은 위를 구현하면 되고 다음은 출력형식을 맞춰보겠습니다. 

필자 또한  반복문 내부에서 K번째 값과 ,를 같이 StringBuilder에 append시켰더니 마지막 요소 뒤에도 ,가 찍히는 일이 발생하였습니다. 그래서 필자는 반복횟수를 조절하여서 큐에 요소가 1개 남을 때까지는 방금 말한 방식으로 appen시켜주고, 큐에 단 하나의 요소가 남은 경우에만 반복문을 탈출해서 K번째 값만 append시키고 >를 닫아주었습니다. 

큐에 요소가 하나만 남았다는 말은 K번째 수는 어차피 자기 자신이기 때문에 로직을 고려할 필요가 없습니다. 

자세한 내용은 소스코드를 참조하시기 바랍니다. 

package Queue;
 
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.concurrent.LinkedBlockingDeque;
 
public class _11866 {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //3번째 수를 연쇄적으로 삭제 
        //3번째 수를 삭제하고 큐를 재구성하는 것은 비효율적
        //큐는 반드시 front에서 값을 꺼내온다. 그렇다고 front의 위치를 임의적으로 옮긴다면  front앞에 있는 수는 나가리가 되버림
        //결론. 삭제하는 수를 front에 오도록 해준다. -> front의 위치에 삭제하는 값으로 이동시킨다. 
        //앞에 있는 수를 뽑아서 rear에 갖다 붙이기
        Scanner sc = new Scanner(System.in);
        
        Deque<Integer> q = new LinkedList<Integer>();
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(sc.nextLine(), " ");
        
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        
        //큐에 값 초기화
        for(int i=1; i<=N;i++) {
            q.offer(i);
        }
        
        sb.append('<');
        
        //아래의 과정을 큐가 빌때까지 반복
        // f           r
        // 1 2 3 4 5 6 7
        // 3번째 수 3을 삭제하기 위해 poll 2번, offer 2번  반복
        
        // f           r
        // 3 4 5 6 7 1 2
        // f값 삭제
        
        // f         r
        // 4 5 6 7 1 2
        while(q.size() > 1) {
            for(int i=0; i<K-1; i++) {
                int val = q.poll();
                q.offer(val);
            }
            sb.append(q.poll()).append(", ");
        }
        
        sb.append(q.poll()).append('>');
        
        
        System.out.println(sb);
        sc.close();
    }
 
}