[Coding/Backjoon] 1021번 회전하는 큐

 

 

 

 

 

문제 링크

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

1021번: 회전하는 큐

 

 

 

1. 구현할 방식

---

큐의 크기 N과 뽑아내려고 하는 갯수 M을 입력받는다. 큐의 크기만큼 자연수가 들어간 큐와 뽑아내려고 하는 수가 들어가있는 큐를 생성한다. 이후 자연수가 들어간 큐에 N까지의 자연수를 추가하고 뽑아낼 수를 차례대로 다른 큐에 추가한다.

while 반복문을 사용하여 자연수 큐와 뽑아낼 수 큐 에서 하나씩 poll 하여 비교하고 만약 다르다면 자연수 큐에서 poll 한 수를 다시 큐에 집어넣고 count 를 1 증가한다.

이후 일치하는 수를 찾았을 때 count 를 (큐 사이즈 - count) 와 비교하여 더 작은 수를 aanswer 에 더한다. 왜냐하면 큐는 한 방향으로만 데이터가 입출력되는 특징이 있다. 따라서 count가 ( Queue size - count ) 작다는 것은 왼쪽으로 이동하였다는 뜻이고 더 크다면 오른쪽으로 이동하였다는 의미이다.

 

 

 

---

 

 

 

2. 코드

---

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {
	public static void main(String[] args) {
    
    	Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();    // 큐의 크기 N
        int M = sc.nextInt();    // 뽑아내려고 하는 갯수 M
        
        Queue<Integer> queue = new LinkedList<Integer>();
        Queue<Integer> find = new LinkedList<Integer>();
        
        IntStream.range(1,N+1).forEach(x->queue.add(x));
        
        int answer = 0;
        
        for(int i =0; i<M; i++) {     //find 큐에 뽑아내려고 하는 데이터 추가
        	int data = sc.nextInt();
            find.add(data);
        }
        
        while(!find.isEmpty()) {
        	int data = find.poll();
            int cnt = 0;
            
            while (data != queue.peek()) {
            	int front = queue.poll();
                queue.add(data);
                cnt++;
            }
            answer += Math.min(cnt,queue.size()-cnt);
            queue.poll();
        }
        System.out.println(answer);
    }
}