[알고리즘] 13. 정렬 기준 만들기
지난 글에서는 빈도수 계산에 대해 정리했습니다. 이번 글에서는 알고리즘 문제에서 매우 자주 등장하는 정렬 기준 만들기에 대해 알아보겠습니다.
정렬은 데이터를 일정한 순서로 나열하는 작업입니다. 숫자를 작은 순서대로 정렬하거나, 문자열을 사전순으로 정렬하거나, 객체를 특정 조건에 맞게 정렬할 때 사용합니다.
정렬의 핵심은 단순히 나열하는 것이 아니라, 어떤 기준으로 앞뒤를 결정할지 정하는 것입니다.
1. 정렬이란?
정렬은 여러 데이터를 정해진 기준에 따라 순서대로 배치하는 것입니다.
예를 들어 숫자 배열이 있다고 하겠습니다.
5 2 8 1 3이 값을 오름차순으로 정렬하면 다음과 같습니다.
1 2 3 5 8반대로 내림차순으로 정렬하면 다음과 같습니다.
8 5 3 2 1정렬은 알고리즘 문제에서 단독으로 나오기도 하고, 다른 풀이를 위한 준비 단계로 사용되기도 합니다.
- 최솟값과 최댓값을 빠르게 찾기
- 중복 값을 인접하게 만들기
- 이분 탐색을 사용하기 위한 준비
- 순위를 계산하기
- 여러 조건에 따라 데이터를 정리하기
2. 오름차순과 내림차순
정렬에서 가장 기본이 되는 기준은 오름차순과 내림차순입니다.
| 구분 | 의미 | 예시 |
|---|---|---|
| 오름차순 | 작은 값에서 큰 값으로 정렬 | 1, 2, 3, 4, 5 |
| 내림차순 | 큰 값에서 작은 값으로 정렬 | 5, 4, 3, 2, 1 |
알고리즘 문제에서는 보통 오름차순 정렬을 먼저 사용합니다. 그 후 문제 조건에 따라 내림차순이나 여러 조건 정렬을 적용합니다.
정렬 문제를 보면 먼저 오름차순인지, 내림차순인지, 아니면 별도의 기준이 있는지 확인해야 합니다.
3. 배열 오름차순 정렬하기
Java에서 배열을 정렬할 때는 Arrays.sort()를 사용할 수 있습니다.
import java.util.Arrays;
int[] numbers = {5, 2, 8, 1, 3};
Arrays.sort(numbers);
System.out.println(Arrays.toString(numbers));출력 결과는 다음과 같습니다.
[1, 2, 3, 5, 8]int 배열에 Arrays.sort()를 사용하면 기본적으로 오름차순으로 정렬됩니다.
4. 배열 내림차순 정렬하기
int[] 같은 기본형 배열은 Collections.reverseOrder()를 바로 사용할 수 없습니다. 내림차순 정렬을 하려면 Integer[] 배열을 사용해야 합니다.
import java.util.Arrays;
import java.util.Collections;
Integer[] numbers = {5, 2, 8, 1, 3};
Arrays.sort(numbers, Collections.reverseOrder());
System.out.println(Arrays.toString(numbers));출력 결과는 다음과 같습니다.
[8, 5, 3, 2, 1]내림차순 정렬이 필요할 때는 int[]와 Integer[]의 차이를 주의해야 합니다.
int[]는 기본형 배열이고, Integer[]는 객체 배열입니다. reverseOrder()는 객체 배열에서 사용할 수 있습니다.
5. 리스트 정렬하기
ArrayList 같은 리스트를 정렬할 때는 Collections.sort()를 사용할 수 있습니다.
import java.util.ArrayList;
import java.util.Collections;
ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(5);
numbers.add(2);
numbers.add(8);
numbers.add(1);
numbers.add(3);
Collections.sort(numbers);
System.out.println(numbers);출력 결과는 다음과 같습니다.
[1, 2, 3, 5, 8]리스트도 기본적으로 오름차순으로 정렬됩니다.
내림차순으로 정렬하려면 다음처럼 사용할 수 있습니다.
Collections.sort(numbers, Collections.reverseOrder());
System.out.println(numbers);[8, 5, 3, 2, 1]6. 문자열 정렬하기
문자열도 정렬할 수 있습니다. 문자열은 기본적으로 사전순으로 정렬됩니다.
import java.util.Arrays;
String[] words = {"banana", "apple", "carrot"};
Arrays.sort(words);
System.out.println(Arrays.toString(words));출력 결과는 다음과 같습니다.
[apple, banana, carrot]사전순 정렬은 문자열 비교 문제나 단어 정렬 문제에서 자주 등장합니다.
7. Comparator란?
기본 정렬이 아니라 직접 기준을 만들고 싶을 때는 Comparator를 사용합니다.
예를 들어 문자열을 사전순이 아니라 길이가 짧은 순서로 정렬하고 싶을 수 있습니다. 이런 경우 직접 정렬 기준을 만들어야 합니다.
import java.util.Arrays;
import java.util.Comparator;
String[] words = {"banana", "kiwi", "apple", "fig"};
Arrays.sort(words, new Comparator<String>() {
@Override
public int compare(String a, String b) {
return a.length() - b.length();
}
});
System.out.println(Arrays.toString(words));출력 결과는 다음과 같습니다.
[fig, kiwi, apple, banana]문자열 길이가 짧은 것부터 긴 것 순서로 정렬되었습니다.
Comparator는 두 값을 비교해서 어떤 값이 앞에 올지 정하는 기준입니다.
8. compare() 반환값 이해하기
Comparator의 compare(a, b)는 두 값을 비교한 뒤 숫자를 반환합니다.
| 반환값 | 의미 |
|---|---|
| 음수 | a가 b보다 앞에 온다 |
| 0 | a와 b의 순서를 바꾸지 않는다 |
| 양수 | b가 a보다 앞에 온다 |
숫자를 오름차순으로 정렬하고 싶다면 보통 a - b를 반환합니다.
return a - b; // 오름차순내림차순으로 정렬하고 싶다면 b - a를 반환합니다.
return b - a; // 내림차순다만 값의 범위가 매우 큰 경우에는 뺄셈 과정에서 오버플로우가 발생할 수 있습니다. 그럴 때는 Integer.compare()를 사용하는 것이 더 안전합니다.
return Integer.compare(a, b); // 오름차순
return Integer.compare(b, a); // 내림차순9. 람다식으로 간단히 정렬하기
Comparator는 람다식을 사용하면 더 짧게 작성할 수 있습니다.
import java.util.Arrays;
String[] words = {"banana", "kiwi", "apple", "fig"};
Arrays.sort(words, (a, b) -> a.length() - b.length());
System.out.println(Arrays.toString(words));출력 결과는 다음과 같습니다.
[fig, kiwi, apple, banana]람다식은 코드를 짧게 만들 수 있지만, 처음에는 compare() 메서드의 의미를 먼저 이해하는 것이 좋습니다.
람다식은 Comparator를 간단히 표현하는 문법입니다. 핵심은 여전히 비교 기준입니다.
10. 여러 조건으로 정렬하기
알고리즘 문제에서는 정렬 기준이 하나만 있는 경우보다 여러 개인 경우가 많습니다.
예를 들어 단어를 다음 기준으로 정렬한다고 해보겠습니다.
- 길이가 짧은 단어가 먼저 온다.
- 길이가 같으면 사전순으로 정렬한다.
이런 경우 먼저 길이를 비교하고, 길이가 같을 때만 사전순 비교를 하면 됩니다.
import java.util.Arrays;
String[] words = {"banana", "apple", "kiwi", "fig", "car"};
Arrays.sort(words, (a, b) -> {
if (a.length() != b.length()) {
return a.length() - b.length();
}
return a.compareTo(b);
});
System.out.println(Arrays.toString(words));출력 결과는 다음과 같습니다.
[car, fig, kiwi, apple, banana]car와 fig는 길이가 3으로 같습니다. 이때 사전순으로 car가 fig보다 앞에 오게 됩니다.
여러 조건 정렬은 1순위 조건을 먼저 비교하고, 같을 때 2순위 조건을 비교합니다.
11. 2차원 배열 정렬하기
2차원 배열을 정렬해야 하는 문제도 자주 나옵니다. 예를 들어 좌표를 정렬한다고 생각해보겠습니다.
정렬 기준은 다음과 같습니다.
- x값이 작은 순서로 정렬한다.
- x값이 같으면 y값이 작은 순서로 정렬한다.
import java.util.Arrays;
int[][] points = {
{3, 4},
{1, 5},
{1, 2},
{2, 3}
};
Arrays.sort(points, (a, b) -> {
if (a[0] != b[0]) {
return a[0] - b[0];
}
return a[1] - b[1];
});
for (int i = 0; i < points.length; i++) {
System.out.println(points[i][0] + " " + points[i][1]);
}출력 결과는 다음과 같습니다.
1 2
1 5
2 3
3 4먼저 x값을 기준으로 정렬하고, x값이 같은 경우 y값을 기준으로 정렬했습니다.
12. 객체 정렬하기
실무나 알고리즘 문제에서는 객체를 정렬해야 하는 경우도 있습니다. 예를 들어 학생의 이름과 점수를 저장한 뒤, 점수가 높은 순서로 정렬할 수 있습니다.
import java.util.ArrayList;
import java.util.Collections;
class Student {
String name;
int score;
Student(String name, int score) {
this.name = name;
this.score = score;
}
}
public class Main {
public static void main(String[] args) {
ArrayList<Student> students = new ArrayList<>();
students.add(new Student("Kim", 80));
students.add(new Student("Lee", 95));
students.add(new Student("Park", 90));
Collections.sort(students, (a, b) -> b.score - a.score);
for (Student student : students) {
System.out.println(student.name + " " + student.score);
}
}
}출력 결과는 다음과 같습니다.
Lee 95
Park 90
Kim 80점수가 높은 학생부터 출력되었습니다. 이처럼 객체 정렬에서는 어떤 필드를 기준으로 정렬할지 정해야 합니다.
13. 객체를 여러 조건으로 정렬하기
학생을 점수순으로 정렬하되, 점수가 같으면 이름순으로 정렬하고 싶을 수도 있습니다.
정렬 기준은 다음과 같습니다.
- 점수가 높은 순서로 정렬한다.
- 점수가 같으면 이름을 사전순으로 정렬한다.
Collections.sort(students, (a, b) -> {
if (a.score != b.score) {
return b.score - a.score;
}
return a.name.compareTo(b.name);
});점수가 다르면 점수 기준으로 정렬하고, 점수가 같을 때만 이름을 비교합니다.
객체 정렬에서는 어떤 필드를 1순위로 볼지, 어떤 필드를 2순위로 볼지 정하는 것이 중요합니다.
14. 정렬 기준을 만들 때 자주 나오는 패턴
정렬 기준은 문제마다 다르지만, 자주 나오는 패턴은 어느 정도 정해져 있습니다.
| 정렬 기준 | Comparator 예시 |
|---|---|
| 숫자 오름차순 | (a, b) -> a - b |
| 숫자 내림차순 | (a, b) -> b - a |
| 문자열 사전순 | (a, b) -> a.compareTo(b) |
| 문자열 길이순 | (a, b) -> a.length() - b.length() |
| 점수 높은 순 | (a, b) -> b.score - a.score |
| x좌표 오름차순, y좌표 오름차순 | if (a[0] != b[0]) return a[0] - b[0]; return a[1] - b[1]; |
처음에는 Comparator 문법보다 “어떤 조건일 때 앞에 와야 하는지”를 먼저 생각하는 것이 좋습니다.
15. 정렬의 시간복잡도
Java의 기본 정렬은 일반적으로 효율적인 정렬 알고리즘을 사용합니다. 알고리즘 문제에서는 보통 정렬의 시간복잡도를 O(N log N)으로 생각하면 됩니다.
| 작업 | 시간복잡도 |
|---|---|
| 배열 정렬 | O(N log N) |
| 리스트 정렬 | O(N log N) |
| 정렬 후 한 번 순회 | O(N log N) + O(N) |
정렬 후 한 번 더 반복문을 돌더라도 전체적으로는 보통 O(N log N)으로 봅니다. N log N이 N보다 더 큰 영향을 주기 때문입니다.
정렬을 사용하는 순간 보통 시간복잡도는 O(N log N)을 먼저 떠올리면 됩니다.
16. 정렬에서 자주 하는 실수
정렬 문제에서는 아래 실수를 자주 하게 됩니다.
- 오름차순과 내림차순 기준을 반대로 작성하는 경우
- int[]에 Collections.reverseOrder()를 사용하려는 경우
- 문자열 사전순 비교에 compareTo()를 사용하지 않는 경우
- 여러 조건 정렬에서 1순위 조건이 같을 때의 처리를 빠뜨리는 경우
- 객체 정렬에서 기준 필드를 잘못 선택하는 경우
- a - b 방식에서 큰 수 오버플로우를 고려하지 않는 경우
특히 여러 조건 정렬에서는 문제에서 요구하는 우선순위를 정확히 읽어야 합니다.
1순위: 점수 높은 순
2순위: 이름 사전순
3순위: 나이 어린 순이런 조건이 있다면 반드시 1순위부터 차례대로 비교해야 합니다.
정렬 기준이 여러 개일 때는 조건의 우선순서를 놓치지 않는 것이 중요합니다.
17. 정리
이번 글에서는 정렬 기준 만들기에 대해 정리했습니다.
- 정렬은 데이터를 특정 기준에 따라 순서대로 배치하는 작업이다.
- 숫자는 기본적으로 오름차순 정렬이 가능하다.
- int[ ] 내림차순 정렬은 Integer[ ]를 사용해야 편하다.
- 문자열은 기본적으로 사전순으로 정렬된다.
- 직접 정렬 기준을 만들 때는 Comparator를 사용한다.
- 여러 조건 정렬은 1순위 조건을 먼저 비교하고, 같을 때 다음 조건을 비교한다.
- 2차원 배열과 객체도 Comparator를 이용해 정렬할 수 있다.
- 정렬의 시간복잡도는 보통 O(N log N)으로 생각한다.
정렬은 알고리즘 문제에서 정말 자주 사용되는 기본 도구입니다. 단순히 sort()를 외우는 것보다, 문제에서 요구하는 정렬 기준을 정확히 코드로 옮기는 연습이 중요합니다.
정렬 문제의 핵심은 “무엇을 기준으로 앞에 둘 것인가”를 정확히 정하는 것입니다.
다음 글 예고
다음 글에서는 예외 케이스 처리법에 대해 알아보겠습니다.
알고리즘 문제에서 자주 틀리는 경계값, 빈 배열, 중복 값, 음수, 최솟값과 최댓값 처리 방법을 정리해보겠습니다.
'Problem Solving > Algorithm' 카테고리의 다른 글
| [알고리즘] 15. 스택(Stack) (0) | 2026.06.28 |
|---|---|
| [알고리즘] 14. 예외 케이스 처리법 (0) | 2026.06.27 |
| [알고리즘] 12. 빈도수 계산 (0) | 2026.06.25 |
| [알고리즘] 11. 카운팅 배열 (0) | 2026.06.24 |
| [알고리즘] 10. 숫자 처리와 자리수 (0) | 2026.06.24 |