도입
코딩테스트에서 정렬은 단순히 숫자를 오름차순으로 나열하는 기술이 아니라, 문제를 더 쉬운 형태로 바꾸는 전처리 전략으로 매우 자주 등장합니다. 정렬을 한 번 해 두면 가장 작은 값이나 큰 값을 쉽게 다룰 수 있고, 인접한 값끼리만 비교해도 되는 구조가 만들어지며, 투 포인터, 이분 탐색, 그리디, 구간 병합 같은 대표 패턴으로 자연스럽게 이어질 수 있습니다.
특히 자바에서는 Arrays.sort, Collections.sort, List.sort, Comparator를 정확히 이해하고 있으면, 직접 정렬 알고리즘을 구현하지 않아도 대부분의 문제를 안정적으로 해결할 수 있습니다. 실제 코딩테스트에서는 정렬 알고리즘 자체 구현보다, 언제 정렬을 먼저 떠올려야 하는지와 어떤 기준으로 정렬해야 하는지를 판단하는 능력이 훨씬 중요합니다.
필요성
정렬 전에는 모든 원소를 서로 비교해야 해서 두 겹 반복문이 필요한 문제도 많습니다. 하지만 정렬을 한 뒤에는 인접한 값만 보거나, 조건을 만족하는 경계를 이분 탐색으로 찾거나, 가장 빠른 종료 시점부터 그리디하게 선택할 수 있게 됩니다. 즉, 정렬은 단순한 보조 기술이 아니라 문제의 시간 복잡도를 바꾸는 핵심 도구입니다.
- 최솟값 / 최댓값 기준 선택 문제
- 회의실 배정, 구간 병합 같은 interval 문제
- 두 수의 합, 차이, 범위 탐색 문제
- 좌표 압축, 순위 매기기 문제
- 문자열 / 객체 다중 조건 정렬 문제
- 정렬 후 인접 비교가 핵심인 문제
- 정렬 + 이분 탐색 결합 문제
판단 신호
- “가장 작은 것부터”, “끝나는 시간이 빠른 순으로” 같은 표현이 보인다.
- 정렬 후 인접 원소끼리만 비교하면 될 것 같다.
- 값의 크기 순서를 이용하면 조건 판별이 쉬워질 것 같다.
- 특정 값 이상 / 이하의 첫 위치를 찾아야 한다.
- 구간들이 겹치는지, 이어지는지 판단해야 한다.
- 원래 값이 아니라 순위나 압축된 번호가 필요하다.
대표 알고리즘
| 알고리즘 | 시간 복잡도 | 특징 | 코테에서의 위치 |
|---|---|---|---|
| 버블 정렬 | O(n²) | 구현은 쉽지만 매우 느림 | 개념 이해용, 실전 사용 거의 없음 |
| 선택 정렬 | O(n²) | 매 단계 최솟값 선택 | 학습용, 실전 사용 거의 없음 |
| 삽입 정렬 | O(n²) | 거의 정렬된 데이터에 상대적으로 강함 | 개념 이해용, 소규모 데이터에서만 제한적 |
| 병합 정렬 | O(n log n) | 분할 정복, 큰 데이터에도 안정적 | 정렬 기반 문제 이해에 중요 |
| 퀵 정렬 | 평균 O(n log n) | 실전에서 빠르지만 최악 O(n²) | 개념 이해용, 라이브러리 활용이 일반적 |
| 힙 정렬 | O(n log n) | 우선순위 기반 처리와 연결됨 | 정렬 자체보다 PriorityQueue 문제에서 중요 |
| 계수 정렬 | O(n + k) | 정수 범위가 작을 때 매우 강력 | 조건만 맞으면 직접 구현 가치가 큼 |
자주 쓰는 정렬 방법
Arrays.sort(arr); // 기본 오름차순
list.sort(Comparator.naturalOrder()); // 리스트 오름차순
list.sort(Comparator.reverseOrder()); // 리스트 내림차순
Arrays.sort(words, Comparator.naturalOrder()); // 객체 배열 정렬
Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0])); // 사용자 기준 정렬int[]는 기본 정렬만 바로 가능하고, Comparator를 쓰려면 Integer[] 같은 객체 배열이 필요합니다.패턴 1. 기본 오름차순 / 내림차순 정렬
가장 기본적인 정렬이지만, 자바에서는 int[]와 Integer[], List<Integer>의 사용 방식이 다릅니다. 특히 내림차순 정렬은 primitive 배열에서 바로 Comparator를 쓸 수 없다는 점을 자주 실수합니다.
int[] nums = {4, 1, 7, 3};
Arrays.sort(nums); // 오름차순
Integer[] arr = {4, 1, 7, 3};
Arrays.sort(arr, Collections.reverseOrder()); // 내림차순
List<Integer> list = new ArrayList<>(Arrays.asList(4, 1, 7, 3));
list.sort(Comparator.reverseOrder());- K번째 수 구하기
- 최솟값 / 최댓값 빠르게 찾기
- 숫자 재배치 문제
- 문자열 사전순 정렬
패턴 2. 다중 조건 정렬
2차원 배열, 객체, 문자열 목록 문제에서는 거의 항상 다중 조건 정렬이 나옵니다. 예를 들어 x좌표 오름차순, 같으면 y좌표 내림차순처럼 기준이 여러 개인 경우가 많습니다.
Arrays.sort(points, (a, b) -> {
if (a[0] != b[0]) return Integer.compare(a[0], b[0]);
return Integer.compare(b[1], a[1]);
});- 좌표 정렬
- 나이순 정렬
- 점수 정렬
- 길이 우선, 사전순 보조 정렬
패턴 3. 정렬 + 그리디
회의실 배정, 구간 선택, 작업 스케줄링 같은 문제는 정렬을 하지 않으면 그리디 기준이 보이지 않습니다. 대표적으로 종료 시간이 빠른 순으로 정렬한 뒤 가능한 회의를 선택하는 패턴이 자주 나옵니다.
Arrays.sort(meetings, (a, b) -> {
if (a[1] != b[1]) return Integer.compare(a[1], b[1]);
return Integer.compare(a[0], b[0]);
});
int count = 0;
int end = 0;
for (int[] meeting : meetings) {
if (meeting[0] >= end) {
count++;
end = meeting[1];
}
}이 패턴은 회의실 배정뿐 아니라, 구간 선택, 최소 제거 문제, 자원 배분 문제에도 자주 확장됩니다.
패턴 4. 정렬 + 구간 병합
interval 문제의 핵심은 구간들을 정렬한 뒤 현재 구간과 직전 구간만 비교해도 된다는 점입니다. 정렬이 없다면 모든 구간을 다 비교해야 해서 비효율적이지만, 정렬 후에는 선형 순회로 병합이 가능합니다.
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> merged = new ArrayList<>();
for (int[] cur : intervals) {
if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < cur[0]) {
merged.add(new int[]{cur[0], cur[1]});
} else {
merged.get(merged.size() - 1)[1] =
Math.max(merged.get(merged.size() - 1)[1], cur[1]);
}
}패턴 5. 정렬 + 투 포인터
두 수의 합, 차이, 특정 범위 내 쌍 찾기 문제는 정렬 후 투 포인터로 많이 해결합니다. 정렬되지 않은 상태에서는 모든 조합을 확인해야 하지만, 정렬 후에는 합이 작으면 왼쪽을 늘리고 크면 오른쪽을 줄이는 식으로 탐색할 수 있습니다.
Arrays.sort(nums);
int left = 0;
int right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
System.out.println("찾음");
break;
} else if (sum < target) {
left++;
} else {
right--;
}
}- 두 수의 합
- 두 수의 차이 최소화
- 용액 / 수열 쌍 문제
- 정렬 후 구간 축소 문제
패턴 6. 정렬 + 이분 탐색
특정 값이 존재하는지, target 이상이 처음 나오는 위치가 어디인지, target보다 큰 값 중 최소가 어디인지 같은 문제는 정렬 후 이분 탐색으로 풀립니다. 자바의 Arrays.binarySearch()를 활용할 수도 있고, 직접 lower bound / upper bound를 구현하기도 합니다.
Arrays.sort(arr);
int idx = Arrays.binarySearch(arr, target);
if (idx >= 0) {
System.out.println("존재함");
} else {
int insertPos = -idx - 1;
System.out.println("삽입 위치: " + insertPos);
}패턴 7. 좌표 압축 / 순위 매기기
좌표 압축은 큰 수나 중복된 값들을 더 작은 인덱스로 치환하는 대표적인 정렬 응용입니다. 정렬 후 중복을 제거하고, 각 값에 순위를 매핑하면 세그먼트 트리, 펜윅 트리, 배열 인덱싱 문제로 쉽게 이어질 수 있습니다.
int[] sorted = Arrays.stream(nums).distinct().sorted().toArray();
Map<Integer, Integer> rank = new HashMap<>();
for (int i = 0; i < sorted.length; i++) {
rank.put(sorted[i], i);
}패턴 8. 계수 정렬
입력 수는 많지만 값의 범위가 작을 때는 O(n log n) 정렬보다 계수 정렬이 더 빠릅니다. 특히 숫자 범위가 제한된 대량 입력 문제에서 자주 고려합니다. 다만 값의 범위가 매우 크면 메모리 낭비가 심해질 수 있으므로 조건을 먼저 확인해야 합니다.
int max = Arrays.stream(nums).max().getAsInt();
int[] count = new int[max + 1];
for (int num : nums) {
count[num]++;
}
int idx = 0;
for (int num = 0; num <= max; num++) {
while (count[num]-- > 0) {
nums[idx++] = num;
}
}- 숫자 범위가 매우 작다.
- 입력 크기가 매우 크다.
- 정렬 기준이 단순한 정수 값이다.
- 메모리로 count 배열을 감당할 수 있다.
패턴 9. 문자열 정렬
문자열 배열은 단순 사전순 정렬만 나오는 것이 아니라, 길이순 정렬, 길이가 같으면 사전순, 특정 위치 문자 기준 정렬 등 다양한 형태로 출제됩니다. 이때 Comparator를 정확히 설계하는 것이 핵심입니다.
Arrays.sort(words, (a, b) -> {
if (a.length() != b.length()) return Integer.compare(a.length(), b.length());
return a.compareTo(b);
});- 단어 정렬
- 파일명 정렬
- 문자열 길이순 정렬
- 사용자 정의 문자열 우선순위 정렬
패턴 10. 정렬 기준 설계 자체가 답인 문제
가장 큰 수 만들기, 로그 정렬, 파일명 정렬, 구간 정렬, 문자열 이어붙이기 최적화 같은 문제는 정렬 기준 자체가 문제의 핵심입니다. 이런 문제는 정렬 기준을 제대로 세우지 못하면 이후 로직이 아무리 좋아도 정답이 되지 않습니다.
Arrays.sort(numsAsString, (a, b) -> (b + a).compareTo(a + b));이런 유형은 “단순 수치 비교”가 아니라, 문제 조건을 비교 함수로 옮기는 능력이 핵심입니다.
자주 하는 실수
- 동점 처리 기준을 빼먹어서 정답과 다른 순서가 나옴
int[]에 바로 내림차순 Comparator를 적용하려고 함a - b방식 비교를 사용해 overflow가 발생함 →Integer.compare(a, b)가 안전함- 정렬 한 번이면 되는데 매 쿼리마다 다시 정렬해서 시간 초과가 남
- 정렬이 필요한 문제인데 Set, Map, Heap만 보고 끝내 버림
- 라이브러리 정렬이 충분한데 불필요하게 직접 구현하다가 실수가 발생함
- 정렬 후 인덱스 의미가 바뀌었는데 원래 인덱스를 따로 관리하지 않음
풀이 루틴
- 정렬하면 비교가 쉬워지는지 먼저 본다.
- 정렬 기준이 무엇인지 정한다.
- 동점일 때 필요한 보조 기준이 있는지 확인한다.
- 정렬 후 투 포인터 / 이분 탐색 / 그리디 / 병합 중 무엇으로 이어질지 본다.
- 정수 범위가 작다면 계수 정렬이 가능한지도 같이 본다.
- primitive 배열인지 객체 배열인지 구분해 적절한 정렬 API를 선택한다.
디버깅
a - b 대신 Integer.compare()를 쓰는지 점검한다.요약
- ✅ 정렬은 코딩테스트에서 브루트포스를 O(n log n) 이하 풀이로 바꾸는 핵심 전처리다.
- ✅ 실제 실전에서는 정렬 알고리즘 직접 구현보다
Arrays.sort,List.sort,Comparator활용이 더 중요하다. - ✅ 다중 조건 정렬, 구간 병합, 투 포인터, 이분 탐색, 좌표 압축 문제에서 매우 자주 등장한다.
- ✅ 정수 범위가 작으면 비교 기반 정렬보다 계수 정렬이 더 적합할 수 있다.
- ✅ 문제를 보면 “정렬 후 무엇이 쉬워지는가”부터 떠올리는 습관이 중요하다.