문제
1부터 N까지의 수가 들어 있는 양방향 순환 큐에서 세 가지 연산(첫 원소 제거, 왼쪽 회전, 오른쪽 회전)을 사용하여 주어진 순서대로 원소를 뽑아낼 때, 2번(왼쪽 회전)과 3번(오른쪽 회전) 연산의 최소 횟수를 구하라.
입력
첫째 줄에 큐 크기 N과 뽑을 수의 개수 M이 주어진다 (N은 50 이하). 둘째 줄에 뽑아내려는 수의 위치가 순서대로 주어진다.
출력
2번, 3번 연산의 최소 실행 횟수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
10 3 1 2 3 | 0 |
풀이
LinkedList를 덱처럼 사용하여 목표 원소가 앞쪽에 가까우면 왼쪽 회전, 뒤쪽에 가까우면 오른쪽 회전하여 최소 연산 횟수를 구한다.
- 1부터 N까지 LinkedList에 넣고 M개의 목표 원소를 순서대로 처리한다
- 목표 원소의 인덱스(idx)를 찾고, 중간점(mid)과 비교한다
- idx가 mid 이하이면 왼쪽 회전(앞에서 빼서 뒤로 넣기)을 idx번 수행한다
- idx가 mid 초과이면 오른쪽 회전(뒤에서 빼서 앞으로 넣기)을 (size-idx)번 수행한다
- 회전 후 첫 원소를 제거하고 다음 목표로 넘어간다
핵심 아이디어: 목표 원소가 큐의 앞쪽 절반에 있으면 왼쪽 회전이, 뒤쪽 절반에 있으면 오른쪽 회전이 더 적은 연산을 사용한다.
코드
package com.ssafy.an.day049;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Day32BOJ1021회전하는큐 { // 1021 회전하는 큐
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
LinkedList<Integer> dq = new LinkedList<>();
for (int n = 1; n <= N; n++) {
dq.offer(n);
}
int M = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int ans = 0;
for (int m = 0; m < M; m++) {
int n = Integer.parseInt(st.nextToken());
int s = dq.size();
int idx = dq.indexOf(n);
int mid = s % 2 == 0 ? s / 2 - 1 : s / 2;
if (idx <= mid) {
for (int i = 0; i < idx; i++) {
dq.offerLast(dq.pollFirst());
ans++;
}
} else {
for (int i = 0; i < s - idx; i++) {
dq.offerFirst(dq.pollLast());
ans++;
}
}
dq.pollFirst();
}
System.out.println(ans);
br.close();
}
}복잡도
- 시간: O(M * N) — 각 목표 원소마다 최대 N/2번 회전
- 공간: O(N) — LinkedList