[JAVA] 백준 1021번 - 회전하는 큐

 

📖 문제

 

📋 코드

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		Queue<Integer> q = new LinkedList<>();
		Queue<Integer> find = new LinkedList<>();

		int N = sc.nextInt();
		int M = sc.nextInt();
		int ans = 0;

		for (int i = 1; i <= N; i++) {
			q.add(i);
		}
		for (int i = 0; i < M; i++) {
			int x = sc.nextInt();
			find.add(x);
		}

		while (!find.isEmpty()) {
			int x = find.poll();
			int cnt = 0;
			while (x != q.peek()) {
				int qFront = q.poll();
				q.add(qFront);
				cnt++;
			}
			ans += Math.min(cnt, q.size() - cnt);
			q.poll();
		}
		System.out.println(ans);
	}
}

👨🏻‍💻 결과

 

📕 풀이 방법

예제 입력 2를 예시로 들자면

Queue<Integer> q = new LinkedList<>();
Queue<Integer> find = new LinkedList<>();

q는 N개의 원소를 포함하고 있는 양방향 순환 큐 <1, 2, 3, 4, 5, 6, 7, 8, 9, 10>
find는 찾아야 하는 수 <2, 9, 5>

 

while (!find.isEmpty()) {
	int x = find.poll();
	// 생략
}

찾아야 하는 수를 하나씩 뽑아내서 x로 저장

 

while (!find.isEmpty()) {
	int x = find.poll();
	int cnt = 0;
	while (x != q.peek()) {
		int qFront = q.poll();
		q.add(qFront);
		cnt++;
	}
	ans += Math.min(cnt, q.size() - cnt);
	q.poll();
}

peek() : 큐의 맨 앞 원소 리턴
poll() : 큐의 맨 앞 원소 리턴 후 삭제

찾아야 하는 원소 x가 큐의 맨 앞에 올 때까지 2번 연산을 반복합니다.

그리고 2번 연산의 수가 cnt로 기록되는데
cnt가 q.size()-cnt 보다 작다면 2번 연산수가 최솟값이고
아니라면 3번 연산수가 최솟값입니다.

 

🔗 링크

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

1021번: 회전하는 큐