[백준 / JAVA] 백준 알고리즘 1015번 수열 정렬

⏰ 2021-06-21 (월) 16:23:31

screener
시리즈 모아보기
백준 알고리즘

17 / 23

Table of Contents

  • 1. 수열 정렬













수열 정렬

랭크사용 언어
JAVA

🔗 🔗 전체 1015번 문제

조건

시간제한메모리 제한
2초128MB

문제

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

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

입력

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

출력

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

케이스

예제 1

  • 입력

TC

1
2
3
2 3 1
  • 출력

TC

1
1 2 0

풀이

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

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

배열 A의 순서 기억하기

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

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

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

ii012
A[i][0]A[i][0]231
A[i][1]A[i][1]012

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

ii012
A[i][0]A[i][0]123
A[i][1]A[i][1]201

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

정렬 후 되돌리기

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

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

이차원 배열 정렬하기

여기서 작은 문제가 하나 생기는데, 바로 정렬이다. 대표적인 정렬 메소드인 Arrays.sort(A);의 경우 1차원 배열에서는 의도에 맞게 동작하나, 그 이상인 nn차원 배열부터는 의도한대로 동작하지 않는다. 또한 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]);
			}
		});
	}
}

분류

  • 정렬

🏷️ 태그
# 백준
# 알고리즘
# JAVA(자바)
# SILVER
# SILVER IV
# 정렬

읽어주셔서 고마워요!

도움이 되셨다면, 공감이나 댓글을 달아주시는 건 어떤가요?

블로그 운영에 큰 힘이 됩니다.

https://hits.seeyoufarm.com/api/count/incr/badge.svg?count_bg=%23484848&icon=react.svg&icon_color=dodgerblue&title=view&title_bg=%23242424&url=https%3A%2F%2Fblog.itcode.dev%2Fposts%2F2021%2F06%2F22%2Fa1015