# 수열 정렬 | 랭크 | 사용 언어 | | :--------------------------------------------------------: | :-----------------------------------------------------------------------------------------------------------------: | | ![image](https://d2gd6pc034wcta.cloudfront.net/tier/7.svg) | ![JAVA](https://shields.io/badge/java-JDK%2014-lightgray?logo=java&style=plastic&logoColor=white&labelColor=orange) | 🔗 [전체 1015번 문제](https://www.acmicpc.net/problem/1015) ## 조건 | 시간제한 | 메모리 제한 | | :------: | :---------: | | 2초 | 128MB | ## 문제 $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 3 2 3 1 ``` + 출력 ``` tc 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를 입력한다. 이를 표로 도식화하면 아래와 같다. | $i$ | 0 | 1 | 2 | | :-------: | :---: | :---: | :---: | | $A[i][0]$ | 2 | 3 | 1 | | $A[i][1]$ | 0 | 1 | 2 | 따라서 배열 $A$를 정렬해도, 순서를 기억할 수 있게 된다. | $i$ | 0 | 1 | 2 | | :-------: | :---: | :---: | :---: | | $A[i][0]$ | 1 | 2 | 3 | | $A[i][1]$ | 2 | 0 | 1 | 위 표는 오름차순 정렬을 적용한 것으로, $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 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 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 1015 풀이 * @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]); } }); } } ``` ## 분류 * 정렬

𝝅번째 알파카의 개발 낙서장

게시글

Table of Contents

😍 읽어주셔서 감사합니다!

도움이 되셨다면, .css-1stu93e{margin:0;font:inherit;color:hotpink;font-weight:700;}💝공감이나 🗨️댓글을 달아주시는 건 어떤가요?

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

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