🔗 Full Problem 1021

Jimin has a bidirectional circular queue containing $N$ elements. Jimin wants to extract several elements from this queue.

Jimin can perform the following three operations on this queue.

1. Extract the first element. Performing this operation turns the original queue elements $a_1, \dotsb, a_k$ into $a_2, \dotsb, a_k$.
2. Shift left by one position. Performing this operation turns $a_1, \dotsb, a_k$ into $a_2, \dotsb, a_k, a_1$.
3. Shift right by one position. Performing this operation turns $a_1, \dotsb, a_k$ into $a_k, a_1, \dotsb, a_{k - 1}$.

The number $N$ originally contained in the queue is given. Also, the positions of the elements Jimin wants to extract are given (these positions refer to the original position in the queue). Write a program that outputs the minimum number of operations 2 and 3 required to extract those elements in the given order.

The first line gives the queue size $N$ and the number of elements to extract $M$. $N$ is a natural number less than or equal to 50, and $M$ is a natural number less than or equal to $N$. The second line gives the positions of the numbers to be extracted, in order. Positions are natural numbers greater than or equal to 1 and less than or equal to N.

Print the answer to the problem on the first line.

INPUT
10 3
1 2 3

OUTPUT
0

INPUT
10 3
2 9 5

OUTPUT
8

INPUT
32 6
27 16 30 11 6 23

OUTPUT
59

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

OUTPUT
14

This problem is easy to understand if you know the characteristics of a queue.

A queue is a data structure in array form where elements are inserted at one end and removed from the other end. Like a conveyor belt, it uses a first-in-first-out (FIFO) approach to process data sequentially, making it useful for handling sequential data.

You can check the characteristics of a queue in the post written on this blog.

However, we need to design a data structure with the following characteristics, not just a plain queue.

1. An operation to extract the first element
2. An operation to shift data left and right (elements at each end wrap around to the opposite end)

Based on this data structure, we implement the operation the algorithm requires.

We must extract the data given in the problem in order, while minimizing the amount of data movement.

When operation 1 is performed, instead of simply erasing the element in the first slot, the slot itself is removed.

In other words, performing operation 1 on a queue with 10 slots reduces the number of slots to 9.

Let's walk through the solution using Example 2. The queue length is 10, as shown above.

The order of elements to extract is shown above.

1. Calculate the position of 2

First, calculate the distance from the first element to extract, 2, to the first slot where the delete operation occurs.

• Right: 9 slots
• Left: 1 slot

Left is faster, so we choose the left direction.

2. Shift the element left

• Cumulative move count: 1

Shift element 2 left by 1 slot to reach the first slot.

3. Delete the element

Delete element 2. Note that the slot itself disappears entirely.

Deletion is not counted in the move count.

4. Calculate the position of 9

Calculate the distance from the second element to extract, 9, to the first slot where the delete operation occurs.

• Right: 3 slots
• Left: 6 slots

Right is faster, so we choose the right direction.

5. Shift the element right

• Cumulative move count: 4

Shift element 9 right by 3 slots to reach the first slot.

6. Delete the element

Delete element 9.

7. Calculate the position of 5

Calculate the distance from the last element to extract, 5, to the first slot where the delete operation occurs.

• Right: 4 slots
• Left: 4 slots

This is a case where the distances are equal. Since the algorithm doesn't impose any additional constraints in this case, moving in either direction is fine.

This document moves left as the standard.

8. Shift the element left

• Cumulative move count: 8

Shift element 9 right by 4 slots to reach the first slot.

9. Delete the element

Delete element 9.

10. Result

The total move count is 8, so the algorithm's result is 8.

JAVA
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;
	}
}

The main operations of a rotating queue are bidirectional movement and deletion. These operations are implemented by the move() and pop() methods, respectively.

JAVA
/**
 * 이동 함수
 *
 * @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());
		}
	}
}

When move() is called, the direction is distinguished by the enum object DIRECTION, and the shift happens the specified number of times.

JAVA
/**
 * 삭제 함수
 */
private static void pop()
{
	QUEUE.removeFirst();
}

When pop() is called, it deletes the first element of the queue.

The core algorithm function is as follows.

JAVA
/**
 * 큐 연산 갯수 반환 함수
 *
 * @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 finds the index of the element to extract.

mid is the midpoint of the queue; direction is set to move right if target is greater than the midpoint, otherwise left.

distance is the distance: when moving right, it's the queue size minus the distance, and when moving left, the distance is used as-is.

Then it moves the calculated direction and distance, and deletes the data. The move distance is accumulated into count.

• Data Structures
• Deque