백준 1021번 : 회전하는 큐 java

이 문제는 덱 자료구조를 이용하여 어떤 방향으로 연산을 해야 더 효율적으로 자료들을 찾을 수 있는지를 구현하는
문제입니다.

위의 문제에서 1 2 3번 연산을 각각 설명해드리도록 하겠습니다.

위와 같은 덱이 있다고 가정해보겠습니다.

만약 제가 찾아야 하는 수가 2라면 표를 왼쪽으로 한번 움직이는 것이 오른쪽으로 5번 움직이는 것보다 적게 움직입니다.

따라서 위 문제에서 2번 연산을 해줍니다.

2번 연산을 해줭 왼쪽으로 표를 한번 움직여주면 다음과 같은 표가 나옵니다.

덱의 맨 앞에 찾고자하는 수인 2가 왔으므로 1번 연산을 해서 2를 덱에서 제거해주도록 하겠습니다.

그럼 다음과 같은 그림이 나옵니다.

이제 6을 찾아보도록 하겠습니다.

6이 현재 있는 인덱스는 3번입니다.

3번에 있는 값을 0번으로 가져오기 위해서는 표를 왼쪽으로 3번 움직이거나 오른쪽으로 2번 움직여야 합니다.

오른쪽으로 2번 움직이는 것이 더 효율적이기 때문에 3번 연산은 2번 실행시켜줍니다.

이제 찾는 수인 6이 덱의 맨 앞으로 왔으니 6을 덱에서 제거합니다.

이와 같은 방식으로 위의 문제를 해결할 수 있습니다.

이제 코드를 보여드리도록 하겠습니다.

---

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int cnt = 0;

        LinkedList<Integer> dq = new LinkedList<>();
        for(int  i = 1; i<=N; i++)
            dq.addLast(i);

        int[] find = new int[M];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<M; i++)
            find[i] = Integer.parseInt(st.nextToken());

        for(int i = 0; i<M; i++){
            if(dq.getFirst() == find[i]){
                dq.removeFirst();
                continue;
            }

            // 2번 연산을 이용했을 때 필요한 연산의 수
            int findIdx = dq.indexOf(find[i]);
            // 3번 연산을 이용했을 때 필요한 연산의 수
            int backCnt = dq.size() - findIdx;

            // 2번 연산 실행
            if(findIdx < backCnt){
                while(dq.getFirst() != find[i]){
                    dq.addLast(dq.removeFirst());
                    cnt++;
                }
            }

            // 3번 연산 실행
            else{
                while(dq.getFirst() != find[i]){
                    dq.addFirst(dq.removeLast());
                    cnt++;
                }
            }

            dq.removeFirst();
        }

        System.out.println(cnt);
    }
}

저는 findIdx, backCnt 변수를 이용하여 어느 쪽으로 이동하는 것이 더 적게 이동해도 되는지를 찾아보았습니다.