백준 1021번 <회전하는 큐>

백준 알고리즘 1021번

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

1021번: 회전하는 큐

---

1021번

N개의 원소를 포함하고 있는 양방향 순환 큐가 있다. 

큐에서는 아래와 같은 3가지 연산을 수행할 수 있다.

1. 첫 번째 원소를 뽑아낸다.
2. 왼쪽으로 한 칸 이동시킨다. a1 ... ak -> a2 ... ak a1
3. 오른쪽으로 한 칸 이동시킨다. a1 ... ak -> ak, a1 ... ak-1

 

큐에 처음 포함되어 있던 수 N과 뽑아내려고 하는 원소의 위치들이 순서대로 주어질 때, 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하여라.

 

입력으로 첫 줄에 큐에 처음 포함되어 있던 수 n과 뽑아내려고 하는 원소의 위치 m이 주어진다. 그 다음 줄에 m개의 위치가 주어진다.

 

출력으로 2번, 3번 연산의 최솟값을 구해서 출력하면 된다.

---

문제 해결

양방향 순환 큐라는 설명을 보고 덱을 사용해야 되는 줄 알고 엄청나게 고민을 했다.

어떻게 2번 연산을 할지 3번 연산을 할지 결정할 수 있는지 진짜 모르겠어서 구글링을 했더니 Deque가 아니라 LinkedList를 써서 indexOf를 사용하는,, 문제 풀이였다,,,

N이 50보다 크지 않기 때문에 가능한 풀이인 것 같다. (그렇지 않았다면 엄청난 시간 초과가 났을 거다,,)

 

LinkedList를 이용하여 뽑아낼 원소의 index를 이용해 2번 연산과 3번 연산을 몇 번 해야 하는지 구할 수 있다.

2번 연산 횟수 : 뽑아낼 원소의 index

3번 연산 횟수 : LinkedList의 크기 - 뽑아낼 원소의 index

---

코드

package bj1021;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] inArr = br.readLine().split(" ");
		int n = Integer.parseInt(inArr[0]);
		int m = Integer.parseInt(inArr[1]);
		LinkedList<Integer> deque = new LinkedList<>();
		for (int i = 1; i < n + 1; i++) {
			deque.add(i);
		}
		inArr = br.readLine().split(" ");
		int answer = 0;
		for (int i = 0; i < m; i++) {
			int select = Integer.parseInt(inArr[i]);
			int front = deque.indexOf(select);
			int back = deque.size() - front;
			if (front > back) {
				for (int j = 0; j < back; j++) {
					int temp = deque.pollLast();
					deque.addFirst(temp);
				}
				answer += back;
			} else {
				for (int j = 0; j < front; j++) {
					int temp = deque.pollFirst();
					deque.addLast(temp);
				}
				answer += front;
			}
			deque.pollFirst();
		}
		System.out.println(answer);
	}

}

---

결과

---