[백준 1021] 회전하는 큐

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

1021번: 회전하는 큐

 

• Deque 자료구조를 이용하면 풀기 수월하다.

 

• 연산 횟수를 세는 경우는 오른쪽으로 한 칸씩 미는 경우와 왼쪽으로 한 칸씩 미는 경우 두 가지이다.
• 한 칸씩 이동하는 이유는 Deque의 첫 번째 값을 뽑아내는 1번 연산을 하기 위함이다.

 

• 찾고자 하는 숫자의 처음 Deque에서의 위치가 주어지면 두 가지 경우로 나뉜다.
  
  
  1. 오른쪽으로 한 칸씩 밀어가며 숫자를 첫 번째 값으로 위치시킬 것인지
  2. 왼쪽으로 한 칸씩 밀어가며 숫자를 첫 번째 값으로 위치시킬 것인지
• 찾고자 하는 숫자의 현재 index가 Deque 크기의 중간보다 작은 수라면 왼쪽으로 민다.
• 찾고자 하는 숫자의 현재 index가 Deque 크기의 중간보다 큰 수라면 오른쪽으로 민다.

 

• 밀 때마다 count를 센다.

 

 

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

public class Main {
	
	static int n, m, count;
	static LinkedList<Integer> deque = new LinkedList<>();
	
	public void solution(int find) {
		int mid;
		if(deque.size()/2==0) mid = deque.size()/2;
		else mid = deque.size()/2;
		
		if(deque.indexOf(find) <= mid) {
			while(deque.peekFirst()!=find) {
				int temp = deque.pollFirst();
				deque.offerLast(temp);
				count++;
			}			
		}
		else {
			while(deque.peekFirst()!=find) {
				int temp = deque.pollLast();
				deque.offerFirst(temp);
				count++;
			}
		}
		int out = deque.pollFirst();
//		System.out.println(out + "  count : " + count + " | size : " + deque.size() + " | mid : " + mid);
	}

	public static void main(String[] args) throws IOException{
		Main T = new Main();
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer stk1 = new StringTokenizer(br.readLine());
		n = Integer.parseInt(stk1.nextToken());
		m = Integer.parseInt(stk1.nextToken());
		count = 0;
		
		for(int i=1; i<=n; i++) deque.add(i);
		
		StringTokenizer stk2 = new StringTokenizer(br.readLine());
		for(int i=0; i<m; i++) {
			int find = Integer.parseInt(stk2.nextToken());
			T.solution(find);
		}
		
		System.out.println(count);
	}
}