[백준] 1021번 회전하는 큐(deQueue_JAVA)

쉬운 문제였는데,

피곤해서 그냥 검색해서 푼 문제..

생각보다 쉬워서 그냥 풀어볼걸 하는 문제였다.

이제 이 유형의 문제는 확실히 풀어야지!

 

---

문제

 

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

1021번: 회전하는 큐

 

 

 

---

설계

알고리즘 설계 [접근 방법] : deQueue 사용

이 문제는 겨우의 수가 3가지이며, 그 중 2번째와 3번째인 경우를 찾으면 된다.

방법 1 : 찾는 수가 가장 앞에 있을 때 그 수를 뺀다.

방법 2 : 가장 앞의 수를 가장 뒤로 옮긴다.

방법 3 : 가장 뒤의 수를 가장 앞으로 옮긴다.

문제에 적합한 메서드를 사용하기 위해 자료구조 LinkedList를 사용했다.

찾는 수가 리스트 가운데보다 앞에 있다면 방법 2를, 리스트 가운데보다 뒤에 있다면 방법 3을 사용한다.

 

 

---

코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

            //리스트 생성
        LinkedList<Integer> queue = new LinkedList();

        int n = sc.nextInt();
        for(int i=1; i<=n; i++) {
            queue.add(i);
        }

            //찾아야하는 수 입력받기
        int m = sc.nextInt();
        int[] arr = new int[m];
        for(int i=0; i<m; i++) {
            arr[i]=sc.nextInt();
        }

            //2번째, 3번째 방법 사용 횟수
        int count=0;

            //찾아야 하는 수 인덱스
        int idx=0;
        while(idx<m) {

            int targetIdx = queue.indexOf(arr[idx]);    //찾아야 하는 수의 인덱스
            int halfIdx = queue.size()/2;            //리스트의 절반 인덱스

            if(targetIdx<=halfIdx) {    //절반보다 앞에 있는 원소라면
                for(int i=0; i<targetIdx; i++) {
                    int temp = queue.pollFirst();    
                    queue.add(temp);                
                    count++;
                }

            } 

            else {    //절반보다 뒤에 있는 원소라면
                for(int i=0; i<queue.size()-targetIdx; i++) {
                    int temp = queue.pollLast();    
                    queue.addFirst(temp);        
                    count++;
                }
            }

                    //가장 앞의 원소를 제거하기
            queue.remove(0);

            idx++;
        }

        //출력
        System.out.println(count);
    }
}

 

 

(❁´◡`❁)

끝!