백준 1021- 회전하는 큐 JAVA

문제, 입출력, 테스트케이스

전형적으로 deque을 이용한 큐 돌리기 문제였다.

처음에는 문제를 잘못 읽어서 테스트케이스 2번이 어떻게 되나 했는데 그냥 시계방향, 반시계방향 돌리면서 해당 원소가 나올 때의 최솟값들을 합하면 된다는 것을 알았다.

 

<문제 접근/풀이과정>
1. 덱을 활용한 원형큐 느낌이 들었음
2. 시계방향, 반시계방향으로 움직이며 원소들을 일일이 확인하고 두 방향 중 최솟값을 answer에 더하면 끝
+참고: 덱은 front, tail부분에 삽입, 삭제, 조회가 가능한 자료구조이다.

 

 

<소스코드>

package boj;

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

public class Boj_1021 {
	public static void main(String[] args) throws IOException {
		// 1번 연산 : poll
		// 2번 연산 : pushright(popleft)
		// 3번 연산 : pushleft(popright)
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz = new StringTokenizer(br.readLine());
		int M = Integer.parseInt(stz.nextToken());
		int N = Integer.parseInt(stz.nextToken());
		int answer = 0;
		Deque<Integer> dq1 = new ArrayDeque<>();
		Deque<Integer> dq2 = new ArrayDeque<>();
		
		for (int i = 1; i <= M; i++) {
			dq1.addLast(i);
			dq2.addLast(i);
		}
		
		stz = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			int target = Integer.parseInt(stz.nextToken()); 
			answer += Math.min(CCW(dq1, target), CW(dq2, target));
		}
		System.out.println(answer);
		
	}

	private static int CW(Deque<Integer> dq, int target) {
		int cnt = 1;
		while(true) {
			int temp = dq.pollLast();
			if(temp == target) {
				return cnt;
			}else {
				cnt++;
				dq.addFirst(temp);
			}
			
		}
	}

	private static int CCW(Deque<Integer> dq, int target) {
		int cnt = 0;
		while(true) {
			int temp = dq.pollFirst();
			if(temp == target) {
				return cnt;
			}else {
				cnt++;
				dq.addLast(temp);
			}
			
		}
	}
}