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

랭크 | 사용 언어 |
---|---|
JAVA |
🔗
시간제한 | 메모리 제한 |
---|---|
2초 | 128MB |
은 부터 까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 를 길이가 인 배열 에 적용하면 길이가 인 배열 가 된다. 적용하는 방법은 이다.
배열 가 주어졌을 때, 수열 를 적용한 결과가 비내림차순이 되는 수열을 찾는 프로그램을 작성하시오. 비내림차순이란, 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우를 말한다. 만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다.
첫째 줄에 배열 의 크기 이 주어진다. 둘째 줄에는 배열 의 원소가 0번부터 차례대로 주어진다. 은 50보다 작거나 같은 자연수이고, 배열의 원소는 1,000보다 작거나 같은 자연수이다.
첫째 줄에 비내림차순으로 만드는 수열 를 출력한다.
- 입력
TC1 2
3 2 3 1
- 출력
TC1
1 2 0
정렬에 대해 잘 알고 있다면 쉬어가는 문제. 한 마디로, 배열 속 요소들을 크기별 등수로 바꾸어 동일한 자리에 표시해주면 된다.
예제의 경우, 배열 가 로 주어졌는데, 이를 오름차순으로 표시하여 배열 로 만들면 이 된다. 즉 이 된다. 의 인덱스를 의 요소의 순서에 맞게 출력하는 것이 알고리즘의 최종 동작이다.
첫 번째로, 정수형 배열의 오름차순 정렬은 매우 쉽다. Arrays.sort(A);
만 적용해주면 될 일이기 때문. 문제는 정렬한 인덱스를 원본 배열 의 순서대로 출력해야 한다는 것.
이를 기억하는 장치로 배열 를 2차원 배열로 만들어 에는 i번째 입력값의 값, 에는 순번 인덱스 i를 입력한다.
이를 표로 도식화하면 아래와 같다.
0 | 1 | 2 | |
---|---|---|---|
2 | 3 | 1 | |
0 | 1 | 2 |
따라서 배열 를 정렬해도, 순서를 기억할 수 있게 된다.
0 | 1 | 2 | |
---|---|---|---|
1 | 2 | 3 | |
2 | 0 | 1 |
위 표는 오름차순 정렬을 적용한 것으로, 을 통해 원래의 순서로 되돌릴 수 있을 것이다.
배열 에 수열 를 적용한 결과인 를 구한다. 위에서 정렬을 통해 크기 순위를 계산했으므로, 이를 위치에 맞게 순서를 되돌려 출력하면 된다.
원래의 위치값은 이 가지고 있으므로, 이 인덱스를 활용하자. 배열 의 식은 와 같은 형태로 계산할 수 있다. 예를 들어, 일 때 정렬된 배열 이므로 이 된다. 이를 코드로 구현하면 완성된다.
여기서 작은 문제가 하나 생기는데, 바로 정렬이다. 대표적인 정렬 메소드인 Arrays.sort(A);
의 경우 1차원 배열에서는 의도에 맞게 동작하나, 그 이상인 차원 배열부터는 의도한대로 동작하지 않는다. 또한 Arrays.sort(A);
는 무조건 오름차순으로만 동작한다.
이를 해결하기 위해선, sort()
메소드를 직접 오버라이딩하면 된다. 물론 아예 구현해도 되지만, 여기서는 기본 API를 최대한 살려 sort 함수를 우리 의도에 맞게 오버라이딩한다.
JAVA1 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
는 다음 요소를 의미하며 반환값이 양수일 경우 현재 요소가 다음 요소보다 뒤로 정렬되며, 반환값이 음수일 경우 현재 요소가 다음 요소보다 앞으로 정렬된다.
JAVA1 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]); } }); } }
- 정렬