[JAVA 알고리즘]BAEKJOON 1021번 회전하는 큐

회전하는 큐

---

문제 설명

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

제한사항

•  없음

입력

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

출력

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

입출력 예

answers	return
10 3 1 2 3	0
10 3  2 9 5	8
32 6 27 16 30 11 6 23	59
10 10 1 6 3 2 7 9 8 4 10 5	14

 

---

나의 문제풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer Q = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(Q.nextToken());
		int M = Integer.parseInt(Q.nextToken());
		Deque<Integer> queue = new ArrayDeque<>();
		int select = 0;
		int cnt = 0;
		
		for (int i = 1; i <= N; i++) {
			queue.add(i);
		}
		
		Q = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			select = Integer.parseInt(Q.nextToken());
			
			if (queue.peek() == select) {
				queue.pop();
			} else {
				Iterator<Integer> it = queue.iterator();
				Iterator<Integer> itr = queue.descendingIterator();
				int left = 0;
				int right = 1;
				
				while (it.hasNext()) {
					if (it.next() == select) break;
					left++;
		        }
				while (itr.hasNext()) {
					if (itr.next() == select) break;
					right++;
		        }
				
				if (left <= right) {
					for (int j = 0; j < left; j++) {
						queue.addLast(queue.pollFirst());
						cnt++;
					}
					queue.pollFirst();
				} else {
					for (int j = 0; j < right; j++) {
						queue.addFirst(queue.pollLast());
						cnt++;
					}
					queue.pollFirst();
				}
			}
		}
		
		System.out.println(cnt);
	}
}

• 주어진 큐의 크기만큼 큐에 숫자를 순차적으로 넣어준다.
• 큐의 첫번째 숫자와 뽑는 숫자가 같으면 해당 숫자를 큐에서 내보낸다.
• 아닐 경우, 이터레이터를 이용해 큐의 정순과 역순으로 해당 숫자 차이를 찾아서 정순, 역순 중 가까운 방향을 찾는다.
• 가까운 방향으로 숫자 차이만큼 정순의 경우 큐의 첫번째첫 번째 숫자를 마지막으로 역순의 경우 큐의 마지막 숫자를 처음으로 옮겨주고 옮기는 횟수를 체크한다. (역순의 경우 첫 번째 숫자가 마지막으로 가 횟수 체크 시 +1을 해주어야 한다.)
• 마지막으로 맨 앞으로 옮긴 해당 숫자를 큐에서 내보낸다.
• 옮기는 횟수를 출력한다.

---

느낀 점

예전에 프로그래머스에서 비슷한 문제를 풀어본 거 같은데 기억이 나지 않았다 그때는 좀 더 간단한 방법으로 풀었던거같은데 이터레이터를 사용하면서 복잡해서 시간이 오래걸릴 줄 알았는데 생각보다 빨라서 시간복잡도에 대해서 나중에 좀더 알아봐야겠다.