[백준, 시뮬레이션, JAVA] P.1021 회전하는 큐

 

1. 아이디어

원형 큐가 떠올라 자바의 LinkedList를 기본적으로 이용하기로 하였습니다.
그다음 값을 꺼낼때 인덱스는 항상 0(큐 이므로)으로 0을 기준으로 왼쪽으로 탐색하여 해당 값을 발견했을때의 count와
오른쪽으로 탐색하여 해당 값을 발견했을때의 count를 비교하여 작은 쪽으로 연산을 진행하여 (1번 혹은 2번) 연산을
수행한다음 값을 꺼내는 방식으로 구현하였습니다. 단, 0이 찾는 값이 바로 있으면 count는 0!!
그리고 왼쪽 방향으로 값을 찾는 연산은 리스트의 마지막 인덱스 ~ 1 까지 연산을 수행하지만 우선적으로 0번째에서 
값을 확인하기 때문에 0번째에 값이 없다면 왼쪽 연산과 달리 count=1로 초기화 해주어야 합니다. 아래는 코드입니다.

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	static int count = 0;

	public static void main(String[] args) {
		LinkedList<Integer> circularQueue = new LinkedList<>();

		Scanner scr = new Scanner(System.in);

		int N = scr.nextInt();
		int M = scr.nextInt();
		boolean[] values = new boolean[N + 1];

		for (int i = 0; i < N; i++) {
			circularQueue.add(i + 1);
		}

		for (int i = 1; i <= M; i++) {
			int checkValue = scr.nextInt();
			count += doIt(circularQueue, circularQueue.size(), checkValue);
		}

		System.out.println(count);
	}

	public static int doIt(LinkedList<Integer> circularQueue, int queueSize, int checkValue) {
		int leftValue = checkLeft(circularQueue, queueSize, checkValue);
		int rightValue = checkRight(circularQueue, queueSize, checkValue);

		boolean direction = leftValue < rightValue ? true : false;

		if (direction) {
			return rotateRight(circularQueue, leftValue);
		} else {
			return rotateLeft(circularQueue, rightValue);
		}
	}

	public static int checkLeft(LinkedList<Integer> circularQueue, int queueSize, int checkValue) {
		int count = 1;

		if (circularQueue.get(0) == checkValue)
			return 0;

		for (int i = queueSize - 1; i >= 0; i--) {
			if (circularQueue.get(i) == checkValue)
				return count;

			count++;
		}
		// 크게 신경쓰지 않아도됨 문제에는 무조건 리스트가 찾으려는 값을 포함하고 있다는 전제가 있기때문에
		return -1;
	}

	public static int checkRight(LinkedList<Integer> circularQueue, int queueSize, int checkValue) {
		int count = 0;

		for (int i = 0; i < queueSize; i++) {
			if (circularQueue.get(i) == checkValue)
				return count;

			count++;
		}

		return -1;
	}

	public static int rotateLeft(LinkedList<Integer> circularQueue, int value) {
		for (int i = 0; i < value; i++) {
			int v = circularQueue.pollFirst();
			circularQueue.addLast(v);
		}
		
		circularQueue.poll();
		
		return value;
	}

	public static int rotateRight(LinkedList<Integer> circularQueue, int value) {
		for (int i = 0; i < value; i++) {
			int v = circularQueue.pollLast();
			circularQueue.addFirst(v);
		}
		
		circularQueue.poll();
		
		return value;
	}
}