[BOJ] 1021: 회전하는 큐(JAVA)
https://www.acmicpc.net/problem/1021
1021번: 회전하는 큐
첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가
www.acmicpc.net
문제
지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.
지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.
- 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
- 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
- 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.
큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.
출력
첫째 줄에 문제의 정답을 출력한다.
예제 입력 1
10 3
1 2 3
예제 출력 1
0
예제 입력 2
10 3
2 9 5
예제 출력 2
8
예제 입력 3
32 6
27 16 30 11 6 23
예제 출력 3
59
예제 입력 4
10 10
1 6 3 2 7 9 8 4 10 5
예제 출력 4
14
[문제 풀이]
덱을 이용하여 해결하면 되는 문제이다.
원하는 수가 덱의 가장 앞에 존재하면 해당 수를 pollFirst()를 이용해서 뽑아내면 된다.
그렇지 않다면, 원하는 수를 뽑아내기 위해서는 덱을 왼쪽으로 회전시킬지, 오른쪽으로 회전시킬지 선택해야하는데, 원하는 수가 덱의 가장 처음에 올 때까지 회전이 필요한 횟수를 비교하여 더 적은 쪽을 선택하면 된다.
그러기 위해서는 왼쪽 회전, 오른쪽 회전을 모두 수행해보아야 하는데, 이를 위해서 덱 하나를 더 선언해주었다.
이름은 t_deq으로 하였고, 현재 deq과 동일한 덱으로 addAll(deq)을 이용해 처음 구현하면 된다.
오른쪽 회전 연산과 왼쪽 회전 연산의 횟수를 비교하기 위해 정수 변수 c1, c2를 선언하고 0으로 초기화한다.
뽑아내길 원하는 수가 덱의 가장 앞에 올 때까지 오른쪽 회전을 하는 횟수를 c1에, 왼쪽 회전하는 횟수를 c2에 저장한다.
오른쪽 회전은 deq을 이용하고, 왼쪽 회전은 t_deq을 이용해서 연산을 진행한다.
모든 연산이 완료되면 c1과 c2를 비교하고 더 작은 값을 선택한다.
1. 만약 c1<=c2라면 오른쪽 회전이 더 연산 횟수가 적거나 같은 것이고 연산은 deq을 이용하였으므로 추가적인 deq 변화는 없고, count에 c1을 더해준다.
2. c1>c2라면 왼쪽 회전이 더 연산 횟수가 적은 것이므로 count에 c2를 더해주고, deq을 t_deq으로 변경한다.
3. 그 후 deq의 가장 앞 원소를 pollFirst()를 이용하여 뽑아낸다.
원하는 모든 수를 뽑아내고 나면 count를 출력하고 종료한다.
[코드]
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
Deque<Integer> deq = new ArrayDeque<>();
int count=0;
for(int i=1;i<=N;i++)
deq.add(i);
for(int i=0;i<M;i++) {
int num = sc.nextInt();
if(deq.peekFirst() == num) deq.pollFirst();
else {
Deque<Integer> t_deq = new ArrayDeque<>();
t_deq.addAll(deq);
int c1=0, c2=0;
while(deq.peekFirst()!=num) {
int temp = deq.pollLast();
deq.addFirst(temp);
c1++;
}
while(t_deq.peekFirst()!=num) {
int temp = t_deq.pollFirst();
t_deq.addLast(temp);
c2++;
}
if(c1<=c2)
count+=c1;
else {
deq = t_deq;
count+=c2;
}
deq.pollFirst();
}
}
System.out.println(count);
}
}