회전하는 큐

---

🔗 🔗 전체 1021번 문제

조건

---

문제

---

지민이는 $N$개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 $a_1, \dotsb, a_k$였던 것이 $a_2, \dotsb, a_k$가 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면 $a_1, \dotsb, a_k$가 $a_2, \dotsb, a_k, a_1$이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면 $a_1, \dotsb, a_k$가 $a_k, a_1, \dotsb, a_{k - 1}$이 된다.

큐에 처음에 포함되어 있던 수 $N$이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

입력

---

첫째 줄에 큐의 크기 $N$과 뽑아내려고 하는 수의 개수 $M$이 주어진다. $N$은 50보다 작거나 같은 자연수이고, $M$은 $N$보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

출력

---

첫째 줄에 문제의 정답을 출력한다.

케이스

---

예제 1

---

INPUT
1
2
10 3
1 2 3

OUTPUT
1
0

예제 2

---

INPUT
1
2
10 3
2 9 5

OUTPUT
1
8

예제 3

---

INPUT
1
2
32 6
27 16 30 11 6 23

OUTPUT
1
59

예제 4

---

INPUT
1
2
10 10
1 6 3 2 7 9 8 4 10 5

OUTPUT
1
14

풀이

---

큐의 특성을 알고 있다면 이해하기 쉬운 문제다.

큐는 배열의 형태로, 한쪽 입구에서 요소의 삽입이 일어나며, 다른 한쪽에서 요소의 삭제가 일어나는 자료구조다. 컨테이너 벨트처럼 순차적으로 데이터를 처리하는 선입선출(FIFO) 방식을 차용하고 있어 순차적인 데이터를 처리하는데 유용하다.

하지만 단순한 큐가 아니라, 아래의 특징을 갖는 자료구조를 설계해야한다.

1. 첫 번째 원소를 뽑아내는 연산
2. 데이터의 좌우 이동 연산 (각 끝의 요소는 반대편으로 이동하는 방식으로 순환)

위 자료구조를 토대로 알고리즘이 원하는 동작을 구현하면 된다.

문제에서 제시하는 데이터를 순서대로 뽑아내되, 최소한의 데이터 이동이 이루어져야한다.

1번 연산을 수행하면, 단순히 첫 번째 칸의 원소만 지우는 게 아니라, 칸 자체를 제거한다.

즉, 10개의 칸을 가진 큐에서 1번 연산을 수행하면 칸이 9개로 감소한다.

예제 풀이

---

예제 2를 기준으로 풀이를 진행한다. 큐의 길이는 총 10으로, 위와 같을 것이다.

뽑을 원소의 순서는 위와 같다.

1. 2의 위치 계산

첫 번째로 뽑을 원소인 2와 데이터의 삭제 연산이 일어나는 첫 번째 칸까지의 위치를 계산한다.

• 오른쪽: 9칸
• 왼쪽: 1칸

왼쪽이 더 빠르므로, 방향을 왼쪽으로 정한다.

2. 요소 왼쪽으로 이동

• 누적 이동횟수: 1

요소 2를 첫 번째 칸까지 왼쪽으로 1칸 이동한다.

3. 요소 삭제

요소 2를 삭제한다. 아예 칸 자체가 사라짐에 유의하자.

삭제는 이동횟수에 포함되지 않는다.

4. 9의 위치 계산

두 번째로 뽑을 원소인 9와 데이터의 삭제 연산이 일어나는 첫 번째 칸까지의 위치를 계산한다.

• 오른쪽: 3칸
• 왼쪽: 6칸

오른쪽이 더 빠르므로, 방향을 오른쪽으로 정한다.

5. 요소 오른쪽으로 이동

• 누적 이동횟수: 4

요소 9를 첫 번째 칸까지 오른쪽으로 3칸 이동한다.

6. 요소 삭제

요소 9를 삭제한다.

7. 5의 위치 계산

마지막으로 뽑을 원소인 5와 데이터의 삭제 연산이 일어나는 첫 번째 칸까지의 위치를 계산한다.

• 오른쪽: 4칸
• 왼쪽: 4칸

거리가 서로 동등한 케이스다. 이 경우 알고리즘 역시 별도의 제약조건을 걸지 않았으므로, 아무 방향으로 이동해도 상관없다.

본 문서에선 왼쪽을 기준으로 이동한다.

8. 요소 왼쪽으로 이동

• 누적 이동횟수: 8

요소 9를 첫 번째 칸까지 오른쪽으로 4칸 이동한다.

9. 요소 삭제

요소 9를 삭제한다.

10. 결과 도출

총 이동횟수는 8회이므로, 알고리즘의 결과는 8이 된다.

전체 소스

---

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * 백준 전체 1021 문제 알고리즘 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/07/14/A1021/">1021 풀이</a>
 * @since 2021.07.14 12:57:01
 */
public class Main
{
	// 뽑을 수의 갯수
	private static int M;
	
	// 큐
	private static final LinkedList<Integer> QUEUE = new LinkedList<>();
	
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		// N과 M
		int[] meta = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		
		// 수의 위치
		int[] position = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		
		// 큐의 크기
		int N = meta[0];
		
		M = meta[1];
		
		// 큐의 크기만큼 큐 초기화
		for (int i = 0; i < N; i++)
		{
			QUEUE.add(i + 1);
		}
		
		writer.write(String.valueOf(solve(position)));
		writer.newLine();
		
		writer.close();
		reader.close();
	}
	
	/**
	 * 큐 연산 갯수 반환 함수
	 *
	 * @param position: [int[]] 수의 위치 배열
	 *
	 * @return [int] 연산 갯수
	 */
	private static int solve(int[] position)
	{
		int count = 0;
		
		for (int i = 0; i < M; i++)
		{
			// 뽑을 요소의 인덱스
			int target = QUEUE.indexOf(position[i]);
			
			// 구간 구분 기준
			int ref = QUEUE.size() / 2;
			
			// 오른쪽으로 이동하는 게 더 빠를 경우
			if (target > ref)
			{
				while (position[i] != QUEUE.getFirst())
				{
					// 맨 끝 요소를 제거하고 맨 앞에 추가
					QUEUE.addFirst(QUEUE.removeLast());
					count++;
				}
			}
			
			// 왼쪽으로 이동하는 게 더 빠를 경우
			else
			{
				while (position[i] != QUEUE.getFirst())
				{
					// 맨 앞 요소를 제거하거 맨 끝에 추가
					QUEUE.addLast(QUEUE.removeFirst());
					count++;
				}
			}
			
			QUEUE.removeFirst();
		}
		
		return count;
	}
}

회전하는 큐의 주요 동작은 양방향 이동, 삭제다. 해당 동작은 각각 move(), pop() 메소드로 구현된다.

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * 이동 함수
 *
 * @param direction: [DIRECTION] 방향 Enum
 * @param distance: [int] 거리
 */
private static void move(DIRECTION direction, int distance)
{
	// 왼쪽으로 이동할 경우
	if (DIRECTION.LEFT == direction)
	{
		for (int i = 0; i < distance; i++)
		{
			QUEUE.addLast(QUEUE.removeFirst());
		}
	}
	
	// 오른쪽으로 이동할 경우
	else
	{
		for (int i = 0; i < distance; i++)
		{
			QUEUE.addFirst(QUEUE.removeLast());
		}
	}
}

move() 수행 시 방향은 enum 객체인 DIRECTION으로 구분하며, 입력한 횟수만큼 이동한다.

JAVA
1
2
3
4
5
6
7
/**
 * 삭제 함수
 */
private static void pop()
{
	QUEUE.removeFirst();
}

pop() 수행 시 큐의 첫 번째 요소를 삭제한다.

핵심 알고리즘 함수는 아래와 같다.

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 큐 연산 갯수 반환 함수
 *
 * @param position: [int[]] 수의 위치 배열
 *
 * @return [int] 연산 갯수
 */
private static int solve(int[] position)
{
	int count = 0;
	
	for (int i = 0; i < M; i++)
	{
		// 뽑을 요소의 인덱스
		int target = QUEUE.indexOf(position[i]);
		
		// 요소의 중간
		int mid = QUEUE.size() / 2;
		
		// 인덱스가 요소의 중간값을 넘을 경우 오른쪽이 더 빠름
		DIRECTION direction = target > mid ? DIRECTION.RIGHT : DIRECTION.LEFT;
		
		// 오른쪽으로 갈 경우 큐의 길이에서 인덱스를 빼서 역계산
		int distance = direction == DIRECTION.RIGHT ? QUEUE.size() - target : target;
		
		move(direction, distance);
		pop();
		
		// 이동 길이 누적
		count += distance;
	}
	
	return count;
}

target으로 뽑을 요소의 인덱스를 구한다.

mid 큐의 중간값으로, target이 중간값보다 클 경우 오른쪽으로, 아닐 경우 왼쪽으로 이동하도록 direction을 지정한다.

distance는 거리로, 오른쪽으로 이동할 경우 큐의 사이즈에서 거리를 빼고, 왼쪽으로 이동할 경우 거리를 그대로 사용한다.

이후 계산한 방향, 거리만큼 이동하고 데이터를 삭제한다. 이동거리는 count에 누적된다.

분류

---

• 자료구조
• 덱