[BOJ] 1021: 회전하는 큐 (JAVA)

문제

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

 

여담

덱을 사용해서 풀어야 하는 것은 알았지만, 원소의 위치를 얻는 메서드가 없어서 당황했다. 풀이를 참고했더니 LinkedList를 사용해서 구현할 수 있다는 것을 알게 되었다..ㅎㅎ 부족한 기본기가 발목을 잡네.. ^^

 

앞으로 원소의 위치를 얻으려면 ArrayList나 LinkedList의 indexOf() 메서드를 사용하자! 

 

풀이

왼쪽과 오른쪽으로 원소를 이동시키기 때문에 덱을 사용해서 문제를 풀면 된다. (양방향 순환 큐 == 덱)

 

2번, 3번 연산의 최솟값을 구하기 위해 뽑아내려고 하는 원소가 왼쪽에 가까운지 오른쪽에 가까운지를 판별해야 한다. 만약 뽑아내려고 하는 원소가 중간보다 앞에 위치한다면 2번 연산을 수행하고, 뒤에 위치한다면 3번 연산을 수행하면 된다. 자세한 내용은 코드를 참고하면 된다. 

 

이때, 주의할 점은 2번 연산을 선택하는 과정에서 중간 위치를 포함시켜야 한다는 점이다. (idx <= mid) 아래의 예시를 통해 그 이유를 살펴보자. 

• 덱의 원소: 1 2 3 4 5, 찾으려는 원소: 3 ⇒ idx = 2, mid = 2
  
  • 2번 연산을 수행하는 경우: 2 3 4 5 1 → 3 4 5 1 2, 총 2번의 연산
  • 3번 연산을 수행하는 경우: 5 1 2 3 4 → 4 5 1 2 3 → 3 4 5 1 2, 총 3번의 연산

따라서 2번 연산을 선택할 때 중간 위치를 포함시켜야 2번, 3번 연산의 최솟값을 찾을 수 있다.

 

코드

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

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());
        LinkedList<Integer> deque = new LinkedList<>();
        for (int i = 1; i <= N; i++) { // 덱에 1 ~ N 넣기
            deque.offer(i);
        }

        st = new StringTokenizer(br.readLine(), " ");
        int[] poll = new int[M];
        for (int i = 0; i < M; i++) {
            poll[i] = Integer.parseInt(st.nextToken());
        }

        int total = 0;
        for (int p : poll) {
            int idx = deque.indexOf(p);
            int mid = deque.size() / 2;

            if (idx <= mid) { // 뽑아내려는 원소가 중간 위치보다 앞이거나 같은 경우
                while (deque.getFirst() != p) {
                    deque.offerLast(deque.pollFirst()); // 2번 연산 수행
                    total++;
                }
            } else { // 뽑아내려는 원소가 중간 위치보다 뒤인 경우
                while (deque.getFirst() != p) {
                    deque.offerFirst(deque.pollLast()); // 3번 연산 수행
                    total++;
                }
            }
            deque.pollFirst(); // 원소 뽑기
        }
        System.out.println(total);
    }
}

---

참고

https://st-lab.tistory.com/216