- [백준 / JAVA] 백준 알고리즘 1021번 회전하는 큐
- [백준 / JAVA] 백준 알고리즘 1020번 디지털 카운터
- [백준 / JAVA] 백준 알고리즘 1019번 책 페이지
- [백준 / JAVA] 백준 알고리즘 1018번 체스판 다시 칠하기
- [백준 / JAVA] 백준 알고리즘 1017번 소수 쌍
- [백준 / JAVA] 백준 알고리즘 1016번 제곱 ㄴㄴ수
👀 [백준 / JAVA] 백준 알고리즘 1015번 수열 정렬
- [백준 / JAVA] 백준 알고리즘 1014번 컨닝
- [백준 / JAVA] 백준 알고리즘 1013번 Contact
- [백준 / JAVA] 백준 알고리즘 1012번 유기농 배추
- [백준 / JAVA] 백준 알고리즘 1011번 Fly me to the Alpha Centauri
- [백준 / JAVA] 백준 알고리즘 1010번 다리 놓기
- [백준 / JAVA] 백준 알고리즘 1009번 분산처리
- [백준 / JAVA] 백준 알고리즘 1008번 A / B
- [백준 / JAVA] 백준 알고리즘 1007번 벡터
- [백준 / JAVA] 백준 알고리즘 1006번 습격자 초라기
- [백준 / JAVA] 백준 알고리즘 1005번 ACM Craft
- [백준 / JAVA] 백준 알고리즘 1004번 어린 왕자
- [백준 / JAVA] 백준 알고리즘 1003번 피보나치 함수
- [백준 / JAVA] 백준 알고리즘 1002번 터렛
- [백준 / JAVA] 백준 알고리즘 1001번 A - B
- [백준 / JAVA] 백준 알고리즘 1000번 A + B
- 백준 알고리즘 시작하기
수열 정렬 🔗
조건 🔗
시간제한 | 메모리 제한 |
---|---|
2초 | 128MB |
문제 🔗
은 부터 까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 를 길이가 인 배열 에 적용하면 길이가 인 배열 가 된다. 적용하는 방법은 이다.
배열 가 주어졌을 때, 수열 를 적용한 결과가 비내림차순이 되는 수열을 찾는 프로그램을 작성하시오. 비내림차순이란, 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우를 말한다. 만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다.
입력 🔗
첫째 줄에 배열 의 크기 이 주어진다. 둘째 줄에는 배열 의 원소가 0번부터 차례대로 주어진다. 은 50보다 작거나 같은 자연수이고, 배열의 원소는 1,000보다 작거나 같은 자연수이다.
출력 🔗
첫째 줄에 비내림차순으로 만드는 수열 를 출력한다.
케이스 🔗
예제 1 🔗
- 입력
TC
0 | 3 |
1 | 2 3 1 |
- 출력
TC
0 | 1 2 0 |
풀이 🔗
정렬에 대해 잘 알고 있다면 쉬어가는 문제. 한 마디로, 배열 속 요소들을 크기별 등수로 바꾸어 동일한 자리에 표시해주면 된다.
예제의 경우, 배열 가 로 주어졌는데, 이를 오름차순으로 표시하여 배열 로 만들면 이 된다. 즉 이 된다. 의 인덱스를 의 요소의 순서에 맞게 출력하는 것이 알고리즘의 최종 동작이다.
배열 A의 순서 기억하기 🔗
첫 번째로, 정수형 배열의 오름차순 정렬은 매우 쉽다. 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 함수를 우리 의도에 맞게 오버라이딩한다.
JAVA
0 | Arrays.sort(A, (next, current) -> { |
1 | // 다음 원소가 현재 원소보다 클 경우 |
2 | if (next[0] < current[0]) |
3 | { |
4 | // 현재 원소를 다음 원소의 뒤로 정렬 |
5 | return 1; |
6 | } |
7 | |
8 | // 다음 원소가 현재 원소보다 작을 경우 |
9 | else if (next[0] > current[0]) |
10 | { |
11 | // 현재 원소를 다음 원소의 앞으로 정렬 |
12 | return -1; |
13 | } |
14 | |
15 | // 다음 원소가 현재 원소와 동일할 경우 |
16 | else |
17 | { |
18 | // 현 위치 유지 |
19 | return 0; |
20 | } |
21 | }) |
Comparater
인터페이스를 lambda 함수의 형태로 구현한 코드다. current
는 현재 요소를, next
는 다음 요소를 의미하며 반환값이 양수일 경우 현재 요소가 다음 요소보다 뒤로 정렬되며, 반환값이 음수일 경우 현재 요소가 다음 요소보다 앞으로 정렬된다.
전체 소스 🔗
JAVA
0 | import java.io.BufferedReader; |
1 | import java.io.BufferedWriter; |
2 | import java.io.IOException; |
3 | import java.io.InputStreamReader; |
4 | import java.io.OutputStreamWriter; |
5 | import java.util.Arrays; |
6 | |
7 | /** |
8 | * 백준 전체 1015 문제 알고리즘 클래스 |
9 | * |
10 | * @author RWB |
11 | * @see <a href="https://blog.itcode.dev/posts/2021/06/22/a1015">1015 풀이</a> |
12 | * @since 2021.06.22 Tue 01:23:31 |
13 | */ |
14 | public class Main |
15 | { |
16 | /** |
17 | * 메인 함수 |
18 | * |
19 | * @param args: [String[]] 매개변수 |
20 | * |
21 | * @throws IOException 데이터 입출력 예외 |
22 | */ |
23 | public static void main(String[] args) throws IOException |
24 | { |
25 | BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); |
26 | BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out)); |
27 | |
28 | // 배열의 크기 |
29 | int N = Integer.parseInt(reader.readLine()); |
30 | |
31 | // 원본 배열 |
32 | int[][] A = new int[N][2]; |
33 | |
34 | // 정렬 배열 |
35 | int[] B = new int[N]; |
36 | |
37 | String[] temp = reader.readLine().split(" "); |
38 | |
39 | StringBuilder builder = new StringBuilder(); |
40 | |
41 | for (int i = 0; i < N; i++) |
42 | { |
43 | A[i][0] = Integer.parseInt(temp[i]); |
44 | A[i][1] = i; |
45 | } |
46 | |
47 | // 정렬 수행 |
48 | sort(A); |
49 | |
50 | for (int i = 0; i < N; i++) |
51 | { |
52 | int index = A[i][1]; |
53 | |
54 | B[index] = i; |
55 | } |
56 | |
57 | for (int b : B) |
58 | { |
59 | builder.append(b).append(" "); |
60 | } |
61 | |
62 | System.out.println(builder.toString().trim()); |
63 | |
64 | writer.close(); |
65 | reader.close(); |
66 | } |
67 | |
68 | /** |
69 | * 정렬 함수 |
70 | * |
71 | * @param A: [int[][]] 대상 배열 |
72 | */ |
73 | private static void sort(int[][] A) |
74 | { |
75 | Arrays.sort(A, (next, current) -> |
76 | { |
77 | // 현재값이 더 클 경우 |
78 | if (next[0] < current[0]) |
79 | { |
80 | return -1; |
81 | } |
82 | |
83 | // 다음값이 더 클 경우 |
84 | else if (next[0] > current[0]) |
85 | { |
86 | return 1; |
87 | } |
88 | |
89 | // 현재값과 다음값이 같을 경우, 사전순 정렬 |
90 | else |
91 | { |
92 | return Integer.compare(next[1], current[1]); |
93 | } |
94 | }); |
95 | } |
96 | } |
분류 🔗
- 정렬
📆 작성일
2021-06-22 Tue 01:23:31
📚 카테고리
🏷️ 태그