🔗 Full Problem 1015

$P[0], P[1], \, \dots \, P[N - 1]$ is a sequence containing each of the numbers from $0$ to $N - 1$ (inclusive) exactly once. Applying sequence $P$ to an array $A$ of length $N$ produces an array $B$ of length $N$. The method of application is $B[P[i]] = A[i]$.

Given array $A$, write a program that finds the sequence $P$ such that the result of applying $P$ is non-decreasing. Non-decreasing means each element is greater than or equal to the element immediately before it. If there are multiple such sequences, print the one that comes first in lexicographic order.

The first line gives the size $N$ of array $A$. The second line gives the elements of array $A$, starting from index 0 in order. $N$ is a natural number less than or equal to 50, and each element of the array is a natural number less than or equal to 1,000.

On the first line, print the sequence $P$ that makes the result non-decreasing.

• Input

TC
3
2 3 1

• Output

TC
1 2 0

If you know sorting well, this is an easy breather of a problem. In short, all you need to do is convert the elements in the array into their rank by size, and mark that rank in the same position.

In the example, array $A$ is given as $[ 2, 3, 1 ]$. Sorting this in ascending order gives array $A1 = [ 1, 2, 3 ]$. In other words, $A1[0] = 1$. The algorithm's final step is to output the index of $A1$ in the order that matches the original elements of $A$.

First, sorting an integer array in ascending order is very easy — all you need is Arrays.sort(A);. The problem is that you need to output the sorted indices in the order of the original array $A$.

To keep track of this, we turn array $A$ into a 2D array, storing the value of the i-th input in $A[i][0]$ and the index i in $A[i][1]$.

This can be diagrammed in a table as follows.

This way, even after sorting array $A$, we can still remember the original order.

The table above shows the result after applying an ascending sort. We can use $A[i][1]$ to restore the original order.

We compute $B$, the result of applying sequence $P$ to array $A$. Since we already computed the rank by size through sorting above, all that's left is to put things back into position and print them.

The original position value is held by $A[i][1]$, so let's use that index. The formula for array $B$ can be computed in the form $B[A[i][1]] = i$. For example, when $i = 1$, the sorted value $A[1][1] = 0$, so $B[0] = 1$. Implementing this in code completes the solution.

There's one small snag here — sorting itself. The go-to sorting method, Arrays.sort(A);, works as intended for a 1D array, but for arrays of 2 or more dimensions, it doesn't behave as intended. Also, Arrays.sort(A); only ever sorts in ascending order.

To solve this, you can override the sort() method directly. Of course, you could implement it entirely from scratch, but here we make the most of the base API and override the sort function to fit our intent.

JAVA
Arrays.sort(A, (next, current) -> {
	// 다음 원소가 현재 원소보다 클 경우
	if (next[0] < current[0])
	{
		// 현재 원소를 다음 원소의 뒤로 정렬
		return 1;
	}

	// 다음 원소가 현재 원소보다 작을 경우
	else if (next[0] > current[0])
	{
		// 현재 원소를 다음 원소의 앞으로 정렬
		return -1;
	}

	// 다음 원소가 현재 원소와 동일할 경우
	else
	{
		// 현 위치 유지
		return 0;
	}
})

This is code that implements the Comparator interface in the form of a lambda function. current refers to the current element, and next refers to the next element. If the return value is positive, the current element is sorted after the next element, and if the return value is negative, the current element is sorted before the next element.

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;

/**
 * 백준 전체 1015 문제 알고리즘 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/06/22/a1015">1015 풀이</a>
 * @since 2021.06.22 Tue 01:23:31
 */
public class Main
{
	/**
	 * 메인 함수
	 *
	 * @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));
		
		// 배열의 크기
		int N = Integer.parseInt(reader.readLine());
		
		// 원본 배열
		int[][] A = new int[N][2];
		
		// 정렬 배열
		int[] B = new int[N];
		
		String[] temp = reader.readLine().split(" ");
		
		StringBuilder builder = new StringBuilder();
		
		for (int i = 0; i < N; i++)
		{
			A[i][0] = Integer.parseInt(temp[i]);
			A[i][1] = i;
		}
		
		// 정렬 수행
		sort(A);
		
		for (int i = 0; i < N; i++)
		{
			int index = A[i][1];
			
			B[index] = i;
		}
		
		for (int b : B)
		{
			builder.append(b).append(" ");
		}
		
		System.out.println(builder.toString().trim());
		
		writer.close();
		reader.close();
	}
	
	/**
	 * 정렬 함수
	 *
	 * @param A: [int[][]] 대상 배열
	 */
	private static void sort(int[][] A)
	{
		Arrays.sort(A, (next, current) ->
		{
			// 현재값이 더 클 경우
			if (next[0] < current[0])
			{
				return -1;
			}
			
			// 다음값이 더 클 경우
			else if (next[0] > current[0])
			{
				return 1;
			}
			
			// 현재값과 다음값이 같을 경우, 사전순 정렬
			else
			{
				return Integer.compare(next[1], current[1]);
			}
		});
	}
}

• Sorting