/ BOJ

BOJ_1021_회전하는큐_JAVA

문제 : 회전하는 큐

링크 : BOJ_1021_회전하는 큐

접근 방식

양방향 순환 큐에서, 원하는 원소를 순서대로 뽑기까지 연산의 최소 횟수를 구하는 문제이다.

이 문제는 현재 위치에서 다음 순서의 숫자를 얻기까지의 최소 횟수를 찾아서 전체 횟수에 더해주면 된다.

양방향 순환 큐이기 때문에, 오른쪽으로 밀었을 때와 왼쪽으로 밀었을 때의 시행횟수를 각각 구하고 그 중에 작은 값을 구해서 더하면 된다.

따라서 양방향 모두 값을 집어넣고 꺼낼 수 있는 덱을 사용하는 것이 핵심이다.

풀이 방법

  1. 인자값 num을 받아 특정 수를 찾을 때까지 « 방향으로 덱을 미는 메서드, » 방향으로 덱을 미는 메서드를 선언한다.

  2. 각 함수는 정의된 방향으로 num을 찾을 때까지 cnt를 증가시켜가며 덱을 순환시키며, num을 찾았을 때 cnt 값을 리턴한다.

  3. deque 2개를 멤버 변수로 선언한다. 2개의 덱은 같은 값이 들어간다. «와 » 각각 최소 횟수를 찾아야 하기 때문에 2개를 선언하였다.

  4. 입력 값을 읽어들여 배열로 저장하고, 배열의 길이만큼 반복한다.

  5. 2개의 덱에 1~N까지 offer시키고 각 방향별로 메서드를 실행시켜 카운트 값을 구한다.

  6. 두 카운트 값 중 더 적은 값을 구해서 누적 cnt 변수에 더한다.

  7. 반복이 모두 종료된 후 누적된 cnt 값을 출력한다.

소스 코드


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

public class BOJ_1021_회전하는큐 {

	static Deque<Integer> deq = new LinkedList<>();
	static Deque<Integer> deq2 = new LinkedList<>();
	// 일단 구현
	public static void main(String[] args) throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String[] str=  in.readLine().split(" ");
		int N = Integer.parseInt(str[0]);
		int M = Integer.parseInt(str[1]);

		int[] arr = new int[M];


		String[] str2 = in.readLine().split(" ");
		for(int i=0;i<M;i++) {
			arr[i] = Integer.parseInt(str2[i]);
		}


		for(int i=1;i<=N;i++) {
			deq.offer(i);
			deq2.offer(i);
		}
		int cntsum = 0;
		for(int i=0;i<M;i++) {
			int cnt1 = forwardSearch(arr[i]);
			int cnt2 = backwardSearch(arr[i]);
			cntsum = cntsum + Math.min(cnt1, cnt2);
			deq.poll();
			deq2.poll();
		}
		System.out.println(cntsum);
	}

	// <<<< 이쪽 방향으로 미는 것을 forward로 하자.
	public static int forwardSearch(int num) {
		int cnt = 0;
		while(deq.peek() != num) {
			deq.offerLast(deq.pollFirst());
			cnt++;
		}
		return cnt;
	}
	// >>> 이쪽 방향으로 미는 것을 backward로 하자.
	public static int backwardSearch(int num) {
		int cnt = 0;
		while(deq2.peek() != num) {
			deq2.offerFirst(deq2.pollLast());
			cnt++;
		}
		return cnt;
	}
}