[알고리즘] 백준 1021 : 회전하는 큐 - JAVA

문제

1021번: 회전하는 큐

문제이해

 

 

입력

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

• N
• M
• M개의 숫자

출력

첫째 줄에 문제의 정답을 출력한다.

---

풀이

 

문제에서 설명하는 큐를 보게 되면 덱(deque)와 같다는 것을 알 수 있습니다.

그렇기에 먼저 덱을 구현 후 왼쪽과 오른쪽 중 타겟과 더 가까운 쪽으로 연산을 수행하면 되겠습니다.

 

---

코드

import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int M = sc.nextInt();
        
        LinkedList<Integer> deque = new LinkedList<>();
        
        for(int i = 1; i <= N; i++){
            deque.offer(i);
        }
        
        int[] nums = new int[M];
        for(int i = 0; i < M; i++){
            nums[i] = sc.nextInt();
        }
        
        int answer = 0;
        for(int target : nums){
            int target_loc = deque.indexOf(target);
            int half_loc = deque.size()/2;
            
            //	오른쪽으로 이동할때 더 가까운 경우
            if(target_loc <= half_loc){
                while(deque.peek() != target){
                    deque.addLast(deque.pollFirst());
                    answer++;
                }
            }
            //	왼쪽으로 이동할때 더 가까운 경우
            else{
                while(deque.peek() != target){
                    deque.addFirst(deque.pollLast());
                    answer++;
                }
            }
            deque.removeFirst();
        }
        System.out.println(answer);
    }
}