수열 정렬

---

🔗 🔗 전체 1015번 문제

조건

---

문제

---

$P[0], P[1], \, \dots \, P[N - 1]$은 $0$부터 $N - 1$까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 $P$를 길이가 $N$인 배열 $A$에 적용하면 길이가 $N$인 배열 $B$가 된다. 적용하는 방법은 $B[P[i]] = A[i]$이다.

배열 $A$가 주어졌을 때, 수열 $P$를 적용한 결과가 비내림차순이 되는 수열을 찾는 프로그램을 작성하시오. 비내림차순이란, 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우를 말한다. 만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다.

입력

---

첫째 줄에 배열 $A$의 크기 $N$이 주어진다. 둘째 줄에는 배열 $A$의 원소가 0번부터 차례대로 주어진다. $N$은 50보다 작거나 같은 자연수이고, 배열의 원소는 1,000보다 작거나 같은 자연수이다.

출력

---

첫째 줄에 비내림차순으로 만드는 수열 $P$를 출력한다.

케이스

---

예제 1

---

• 입력

TC
1
2
3
2 3 1

• 출력

TC
1
1 2 0

풀이

---

정렬에 대해 잘 알고 있다면 쉬어가는 문제. 한 마디로, 배열 속 요소들을 크기별 등수로 바꾸어 동일한 자리에 표시해주면 된다.

예제의 경우, 배열 $A$가 $[ 2, 3, 1 ]$로 주어졌는데, 이를 오름차순으로 표시하여 배열 $A1$로 만들면 $[ 1, 2, 3 ]$이 된다. 즉 $A1[0] = 1$이 된다. $A1$의 인덱스를 $A$의 요소의 순서에 맞게 출력하는 것이 알고리즘의 최종 동작이다.

배열 A의 순서 기억하기

---

첫 번째로, 정수형 배열의 오름차순 정렬은 매우 쉽다. Arrays.sort(A);만 적용해주면 될 일이기 때문. 문제는 정렬한 인덱스를 원본 배열 $A$의 순서대로 출력해야 한다는 것.

이를 기억하는 장치로 배열 $A$를 2차원 배열로 만들어 $A[i][0]$에는 i번째 입력값의 값, $A[i][1]$에는 순번 인덱스 i를 입력한다.

이를 표로 도식화하면 아래와 같다.

따라서 배열 $A$를 정렬해도, 순서를 기억할 수 있게 된다.

위 표는 오름차순 정렬을 적용한 것으로, $A[i][1]$을 통해 원래의 순서로 되돌릴 수 있을 것이다.

정렬 후 되돌리기

---

배열 $A$에 수열 $P$를 적용한 결과인 $B$를 구한다. 위에서 정렬을 통해 크기 순위를 계산했으므로, 이를 위치에 맞게 순서를 되돌려 출력하면 된다.

원래의 위치값은 $A[i][1]$이 가지고 있으므로, 이 인덱스를 활용하자. 배열 $B$의 식은 $B[A[i][1]] = i$와 같은 형태로 계산할 수 있다. 예를 들어, $i = 1$일 때 정렬된 배열 $A[1][1] = 0$이므로 $B[0] = 1$이 된다. 이를 코드로 구현하면 완성된다.

이차원 배열 정렬하기

---

여기서 작은 문제가 하나 생기는데, 바로 정렬이다. 대표적인 정렬 메소드인 Arrays.sort(A);의 경우 1차원 배열에서는 의도에 맞게 동작하나, 그 이상인 $n$차원 배열부터는 의도한대로 동작하지 않는다. 또한 Arrays.sort(A);는 무조건 오름차순으로만 동작한다.

이를 해결하기 위해선, sort() 메소드를 직접 오버라이딩하면 된다. 물론 아예 구현해도 되지만, 여기서는 기본 API를 최대한 살려 sort 함수를 우리 의도에 맞게 오버라이딩한다.

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Arrays.sort(A, (next, current) -> {
	// 다음 원소가 현재 원소보다 클 경우
	if (next[0] < current[0])
	{
		// 현재 원소를 다음 원소의 뒤로 정렬
		return 1;
	}

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

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

Comparater 인터페이스를 lambda 함수의 형태로 구현한 코드다. current는 현재 요소를, next는 다음 요소를 의미하며 반환값이 양수일 경우 현재 요소가 다음 요소보다 뒤로 정렬되며, 반환값이 음수일 경우 현재 요소가 다음 요소보다 앞으로 정렬된다.

전체 소스

---

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
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]);
			}
		});
	}
}

분류

---

• 정렬