https://www.acmicpc.net/problem/1021
문제
> 지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다.
> 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.
> 지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.
1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.
> 큐에 처음에 포함되어 있던 수 N이 주어진다.
> 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다.
(이 위치는 가장 처음 큐에서의 위치이다.)
> 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.접근
회전하는 큐 이기 때문에 deque를 사용하여 구현한다.
기본적으로 1번의 연산은 연산횟수로 치지 않기 때문에 2,3번 연산을 계속하며 1번 연산을 쓸 수 있게 첫 원소가 원하는 수가 될 때까지 반복하면된다.
최소의 2,3번 연산을 위해선 현재 첫 원소 기준 2번연산을 쭉 해서 원하는 원소를 찾을 때의 연산 수와 3번을 쭉했을 때의 연산 수 중 더 작은 수가 된다.
즉, 만약 큐의 크기가 8이면 특정 원소를 찾기 위해 2번연산을 5번했다면, 이는 3번 연산으론 3번만에 할 수 있다는 뜻이된다.
따라서 2번이나 3번연산으로 쭉 밀고 크기-연산횟수 한 수와 최소연산을 해서 구해내면된다.
문제해결
> N과 M을 입력받고 deque를 선언한 뒤 1부터 N까지 큐에 넣는다.
> 최종 연산 횟수를 누적할 rst변수를 선언하고, 원하는 수 M개를 찾기위해 M번 반복문을 돈다.
> 내부에서 각 수를 찾기 위한 연산횟수를 cmd로 나타낸다.
> while문을 통해 첫 원소가 원하는 원소가 될 때까지 반복하며 cmd를 누적하고 2번연산을 수행한다.
> 2번연산은 pollFirst로 첫 원소를 제거함과 동시에 offerLast로 맨 뒤에 넣어주며 수행한다.
> 누적된 cmd와 현 dq의 크기-cmd한 값중 Math.min으로 더 작은 값을 구한다.
> 크기-cmd값이 선택되면 이는 3번 연산이 더 효율적이다 라는 뜻이된다.
> 갱신된 최적의 cmd를 rst에 누적히고 출력한다. 코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//1021번 회전하는 큐
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
Deque<Integer> dq = new ArrayDeque<>();
for(int i = 1; i <= N; i++) dq.offer(i);
st = new StringTokenizer(br.readLine());
int rst = 0;
for(int i = 0; i < M; i++) {
int t = Integer.parseInt(st.nextToken());
int cmd = 0;
while(dq.getFirst() != t) {
cmd++;
dq.offerLast(dq.pollFirst());
}
cmd = Math.min(cmd, dq.size()-cmd);
dq.pollFirst();
rst += cmd;
}
System.out.print(rst);
}
}
후기
Deque의 원리를 알면 쉬운문제다
