[백준] 1021번 : 회전하는 큐

문제

n개의 원소를 가진 양방향 큐에서 아래와 같은 연산을 수행하여

주어진 순서대로 원소를 뽑을 때 2, 3번 연산의 최솟값을 구하라

 

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

 

접근 방식

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

위와 같은 값을 가진 큐가 주어졌을 때

{2, 9, 5}

순서대로 값을 뽑아내려면

2번과 3번 연산이 몇 번 필요한지 구해야 한다.

 

각각의 연산은 아래처럼 ArrayDeque, LinkedList 등에서 제공해 주는

deque.pollFirst(), deque.offerLast(deque.pollFirst()), deque.offerFirst(deque.pollLast())

메서드를 사용해서 수행하면 될 것 같다

(참고로 offer()메서드는 가장 뒤의, poll() 메서드는 가장 앞의 데이터를 삭제한다)

 

왼쪽 혹은 오른쪽 중에서 어디로 이동시키는 것이

가장 효율적인지는 중앙을 기준으로 판단하면 된다.

 

만약 2번 값을 뽑으려면 2번 인덱스는 중앙보다 전에 있으니

왼쪽으로 이동시키는 것이 가장 빠를 것이고

중앙보다 뒤에 있는 인덱스의 경우에는 오른쪽으로 이동시키는 것이 가장 빠르다.

 

그 후에 카운트하는 변수를 하나 선언한 후

2번과 3번 연산마다 카운트를 올려준다.

 

풀이

public class Main {

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

		StringTokenizer input1 = new StringTokenizer(br.readLine());
		List<String> orders = Arrays.stream(br.readLine().split(" "))
			.collect(Collectors.toList());

		int n = Integer.parseInt(input1.nextToken());
		int m = Integer.parseInt(input1.nextToken());

		int[] result = new int[m];
		int idx = 0;

		int count = 0;

		LinkedList<Integer> deque = new LinkedList<>();

		for (int i = 1; i <= n; i++) {
			deque.offer(i);
		}

		while (idx <= m - 1) {
			String order = orders.get(idx);
			int targetIdx = deque.indexOf(Integer.parseInt(order));

			while (!(deque.peekFirst() + "").equals(order)) {
				int mid = (int)(deque.size() / 2.0);

				if (targetIdx <= mid) {
					deque.offerLast(deque.poll());
					count++;
				} else if (targetIdx > mid){
					deque.offerFirst(deque.pollLast());
					count++;
				} else {
					deque.poll();
				}
			}

			if ((deque.peekFirst() + "").equals(order)) {
				result[idx++] = deque.poll();
			}
		}

		System.out.println(count);
	}
}