코딩테스트에서 정렬은 핵심 중의 핵심이다!
오늘 글에서는 자바(Java)로 코딩 테스트를 준비하는 분들을 위해, 꼭 알아야 할 정렬에 대한 모든 것을 알아보도록 하겠다.
💡 정렬이란?
정렬(Sorting)은 데이터들을 특정한 기준에 따라 순서대로 나열하는 것을 의미합니다. 오름차순(작은 값에서 큰 값으로) 또는 내림차순(큰 값에서 작은 값으로)으로 정렬할 수 있습니다.
예를 들어, [5, 2, 8, 1, 3]이라는 배열을 오름차순으로 정렬하면 [1, 2, 3, 5, 8]이 됩니다.
📝 자바에서 정렬하는 가장 쉬운 방법: Arrays.sort()와 Collections.sort()
자바에서는 편리하게 정렬을 할 수 있도록, Arrays.sort()와 Collections.sort() 메서드를 제공합니다.
이 두 메서드만 잘 활용해도 대부분의 코딩 테스트 정렬 문제는 해결할 수 있습니다.
(1) 기본 타입 배열 정렬: Arrays.sort()
Arrays.sort()는 int[], double[], char[] 등 기본 타입(primitive type) 배열을 정렬할 때 사용합니다.
내부적으로는 듀얼-피봇 퀵소트(Dual-Pivot Quicksort) 알고리즘을 사용하며, 이는 평균적으로 O(NlogN)의 시간 복잡도를 가집니다.
import java.util.Arrays;
public class BasicArraySort {
public static void main(String[] args) {
// 1. int 배열 오름차순 정렬
int[] intArray = {5, 2, 8, 1, 3};
System.out.println("정렬 전: " + Arrays.toString(intArray));
Arrays.sort(intArray); // 오름차순 정렬
System.out.println("정렬 후: " + Arrays.toString(intArray)); // 출력: [1, 2, 3, 5, 8]
// 2. String 배열 오름차순 정렬 (알파벳 순서)
String[] stringArray = {"apple", "banana", "kiwi", "grape"};
System.out.println("정렬 전: " + Arrays.toString(stringArray));
Arrays.sort(stringArray);
System.out.println("정렬 후: " + Arrays.toString(stringArray)); // 출력: [apple, banana, grape, kiwi]
}
}// 출력 결과
정렬 전: [5, 2, 8, 1, 3]
정렬 후: [1, 2, 3, 5, 8]
정렬 전: [apple, banana, kiwi, grape]
정렬 후: [apple, banana, grape, kiwi](2) 객체 배열 또는 리스트 정렬: Arrays.sort() & Collections.sort()
객체 배열(Integer[], String[] 등) 또는 List 계열 컬렉션(ArrayList, LinkedList 등)을 정렬할 때는 Arrays.sort() (객체 배열용) 또는 Collections.sort() (List용)를 사용합니다.
이들은 내부적으로 TimeSort 알고리즘을 사용하며, 이는 안정적인(stable) 정렬이면서 O(NlogN)의 시간복잡도를 가집니다.
Integer 배열 정렬
import java.util.Arrays;
public class ObjectArraySort {
public static void main(String[] args) {
Integer[] integerArray = {5, 2, 8, 1, 3};
System.out.println("정렬 전: " + Arrays.toString(integerArray));
Arrays.sort(integerArray); // Integer 배열도 오름차순 정렬
System.out.println("정렬 후: " + Arrays.toString(integerArray)); // 출력: [1, 2, 3, 5, 8]
}
}// 출력 결과
정렬 전: [5, 2, 8, 1, 3]
정렬 후: [1, 2, 3, 5, 8]List 정렬
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class ListSort {
public static void main(String[] args) {
List<Integer> numbers = new ArrayList<>();
numbers.add(5);
numbers.add(2);
numbers.add(8);
numbers.add(1);
numbers.add(3);
System.out.println("정렬 전: " + numbers);
Collections.sort(numbers); // 오름차순 정렬
System.out.println("정렬 후: " + numbers); // 출력: [1, 2, 3, 5, 8]
}
}// 출력 결과
정렬 전: [5, 2, 8, 1, 3]
정렬 후: [1, 2, 3, 5, 8]🔄 내림차순 정렬은 어떻게 할까요?
기본 sort 메서드는 오름차순 정렬을 수행합니다.
내림차순 정렬을 하고 싶다면, Comparator를 사용해야 합니다.
(1) Integer 배열/리스트 내림차순 정렬
Collections.reverseOrder()를 사용하면 간편하게 내림차순 정렬을 할 수 있습니다.
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.ArrayList;
public class DescendingSort {
public static void main(String[] args) {
// Integer 배열 내림차순 정렬
Integer[] integerArray = {5, 2, 8, 1, 3};
System.out.println("배열 정렬 전: " + Arrays.toString(integerArray));
Arrays.sort(integerArray, Collections.reverseOrder());
System.out.println("배열 정렬 후 (내림차순): " + Arrays.toString(integerArray)); // 출력: [8, 5, 3, 2, 1]
// List 내림차순 정렬
List<Integer> numbers = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 3));
System.out.println("리스트 정렬 전: " + numbers);
Collections.sort(numbers, Collections.reverseOrder());
System.out.println("리스트 정렬 후 (내림차순): " + numbers); // 출력: [8, 5, 3, 2, 1]
}
}// 출력 결과
배열 정렬 전: [5, 2, 8, 1, 3]
배열 정렬 후 (내림차순): [8, 5, 3, 2, 1]
리스트 정렬 전: [5, 2, 8, 1, 3]
리스트 정렬 후 (내림차순): [8, 5, 3, 2, 1]💻 커스텀 정렬: Comparator를 활용하자!
코딩테스트에서는 단순히 오름차순/내림차순이 아니라, 특정 기준에 따라 객체를 정렬해야 하는 경우가 많습니다.
이때 Comparator 인터페이스를 구현하거나 람다식을 사용하여 정렬 기준을 직접 정의할 수 있습니다.
Comparator는 compare(T o1, T o2) 메서드를 오버라이드하여 두 객체 o1과 o2의 비교 결과를 반환합니다.
o1<o2: 음수 반환o1같음o2: 0 반환- 여기서 '같다'라는 건, "두 객체가 정렬 기준에 따라 동등하다"라는 의미로, 자바에서의
equals()메서드나==연산자의 의미와는 다릅니다. - o1과 o2가 정렬 기준에 있어서 순서상 차이가 없다는 것을 의미합니다.
- 여기서 '같다'라는 건, "두 객체가 정렬 기준에 따라 동등하다"라는 의미로, 자바에서의
o1>o2: 양수 반환
(1) 문자열 길이 순으로 정렬하기
import java.util.Arrays;
import java.util.Comparator;
public class CustomSortStringLength {
public static void main(String[] args) {
String[] words = {"apple", "kiwi", "banana", "grape"};
// 문자열 길이를 기준으로 오름차순 정렬
// 길이가 같으면 사전순으로 정렬 (compareTo 사용)
Arrays.sort(words, new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
if (s1.length() != s2.length()) {
return s1.length() - s2.length(); // 길이 다르면 길이로 비교
} else {
return s1.compareTo(s2); // 길이 같으면 사전순으로 비교
}
}
});
System.out.println("길이 순 정렬 (오름차순): " + Arrays.toString(words));
// 출력: [kiwi, apple, grape, banana]
// 람다식으로 더 간결하게 표현 가능!
Arrays.sort(words, (s1, s2) -> {
if (s1.length() != s2.length()) {
return s1.length() - s2.length();
} else {
return s1.compareTo(s2);
}
});
System.out.println("길이 순 정렬 (람다): " + Arrays.toString(words));
}
}// 출력 결과
길이 순 정렬 (오름차순): [kiwi, apple, grape, banana]
길이 순 정렬 (람다): [kiwi, apple, grape, banana](2) 2차원 배열 정렬: 행(row) 기준으로 정렬하기
좌표 평면의 점을 나타내는 int[][] 배열을 정렬할 때 유용합니다. 첫 번째 원소를 기준으로 정렬하고, 첫 번째 원소가 같으면 두 번째 원소를 기준으로 정렬하는 방식이 흔합니다.
import java.util.Arrays;
import java.util.Comparator;
public class CustomSort2DArray {
public static void main(String[] args) {
int[][] points = {{3, 4}, {1, 2}, {5, 0}, {1, 5}};
// 첫 번째 원소 (x 좌표) 기준으로 오름차순 정렬
// x 좌표가 같으면 두 번째 원소 (y 좌표) 기준으로 오름차순 정렬
Arrays.sort(points, new Comparator<int[]>() {
@Override
public int compare(int[] p1, int[] p2) {
if (p1[0] != p2[0]) {
return p1[0] - p2[0]; // x 좌표 다르면 x 좌표로 비교
} else {
return p1[1] - p2[1]; // x 좌표 같으면 y 좌표로 비교
}
}
});
System.out.println("2차원 배열 정렬 (x 기준 오름차순, y 기준 오름차순):");
for (int[] point : points) {
System.out.println(Arrays.toString(point));
}
/*
출력:
[1, 2]
[1, 5]
[3, 4]
[5, 0]
*/
System.out.println("--- 람다식으로 간결하게 ---");
// 람다식으로 표현
Arrays.sort(points, (p1, p2) -> {
if (p1[0] != p2[0]) {
return p1[0] - p2[0];
} else {
return p1[1] - p2[1];
}
});
for (int[] point : points) {
System.out.println(Arrays.toString(point));
}
}
}// 출력 결과
2차원 배열 정렬 (x 기준 오름차순, y 기준 오름차순):
[1, 2]
[1, 5]
[3, 4]
[5, 0]
--- 람다식으로 간결하게 ---
[1, 2]
[1, 5]
[3, 4]
[5, 0](3) 사용자 정의 객체 정렬: Comparable vs Comparator
만약 직접 만든 클래스의 객체들을 정렬하고 싶다면 두 가지 방법이 있습니다.
3-1. Comparable 인터페이스 구현
클래스 자체에 기본 정렬 기준을 정의하고 싶을 때 Comparable 인터페이스를 구현합니다. compareTo(T o) 메서드를 오버라이드하여 자기 자신(this)과 비교 대상(o)을 비교합니다.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
class Person implements Comparable<Person> {
String name;
int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public int compareTo(Person other) {
// 나이 기준으로 오름차순 정렬 (기본 정렬)
return this.age - other.age;
}
@Override
public String toString() {
return "Person{" + "name='" + name + '\'' + ", age=" + age + '}';
}
}
public class ComparableExample {
public static void main(String[] args) {
List<Person> people = new ArrayList<>();
people.add(new Person("Alice", 30));
people.add(new Person("Bob", 25));
people.add(new Person("Charlie", 30));
people.add(new Person("David", 20));
System.out.println("정렬 전: " + people);
Collections.sort(people); // Person 클래스의 compareTo() 메서드 기준으로 정렬
System.out.println("정렬 후 (나이 오름차순): " + people);
/*
출력:
[Person{name='David', age=20}, Person{name='Bob', age=25}, Person{name='Alice', age=30}, Person{name='Charlie', age=30}]
*/
}
}// 출력 결과
정렬 전: [Person{name='Alice', age=30}, Person{name='Bob', age=25}, Person{name='Charlie', age=30}, Person{name='David', age=20}]
정렬 후 (나이 오름차순): [Person{name='David', age=20}, Person{name='Bob', age=25}, Person{name='Alice', age=30}, Person{name='Charlie', age=30}]3-2. Comparator 인터페이스 사용
Comparable은 하나의 기본 정렬 기준만 정의할 수 있습니다. 만약 다양한 정렬 기준으로 정렬하고 싶거나, 클래스를 수정할 수 없는 경우라면 Comparator를 사용합니다.
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
// Person 클래스는 위와 동일하다고 가정
// class Person implements Comparable<Person> {...}
public class ComparatorExample {
public static void main(String[] args) {
List<Person> people = new ArrayList<>();
people.add(new Person("Alice", 30));
people.add(new Person("Bob", 25));
people.add(new Person("Charlie", 30));
people.add(new Person("David", 20));
// 나이 내림차순 정렬 (Comparator 사용)
Collections.sort(people, new Comparator<Person>() {
@Override
public int compare(Person p1, Person p2) {
return p2.age - p1.age; // 내림차순
}
});
System.out.println("정렬 후 (나이 내림차순): " + people);
/*
출력:
[Person{name='Alice', age=30}, Person{name='Charlie', age=30}, Person{name='Bob', age=25}, Person{name='David', age=20}]
*/
// 이름 오름차순 정렬 (람다식 Comparator 사용)
// 나이가 같으면 이름으로 정렬하고 싶다면?
// p1.name.compareTo(p2.name) -> 사전순 오름차순
Collections.sort(people, (p1, p2) -> {
if (p1.age != p2.age) {
return p1.age - p2.age; // 나이가 다르면 나이 오름차순
} else {
return p1.name.compareTo(p2.name); // 나이가 같으면 이름 오름차순
}
});
System.out.println("정렬 후 (나이 오름차순, 나이 같으면 이름 오름차순): " + people);
/*
출력:
[Person{name='David', age=20}, Person{name='Bob', age=25}, Person{name='Alice', age=30}, Person{name='Charlie', age=30}]
*/
}
}// 출력 결과
정렬 후 (나이 내림차순): [Person{name='Alice', age=30}, Person{name='Charlie', age=30}, Person{name='Bob', age=25}, Person{name='David', age=20}]
정렬 후 (나이 오름차순, 나이 같으면 이름 오름차순): [Person{name='David', age=20}, Person{name='Bob', age=25}, Person{name='Alice', age=30}, Person{name='Charlie', age=30}]📈 정렬 시 시간 복잡도 고려하기
대부분의 코딩 테스트 문제에서 N의 크기가 10^5 정도라면 O(NlogN)의 정렬 알고리즘은 무리 없이 통과합니다.
하지만 N이 10^6 이상이라면 정렬 시간이 중요한 고려사항이 될 수 있습니다.
- O(NlogN) 정렬:
Arrays.sort(),Collections.sort()(퀵소트, 병합 정렬 기반) - O(N^2) 정렬: 버블 정렬, 선택 정렬, 삽입 정렬 (코딩 테스트에서 거의 사용하지 않음, 매우 비효율적)
중요: 코딩 테스트에서 직접 정렬 알고리즘(퀵소트, 병합 정렬 등)을 구현하는 경우는 드뭅니다.
대부분 Arrays.sort()나 Collections.sort()를 잘 활용하고, Comparator로 커스텀 정렬 로직을 구현하는 것이 핵심입니다.
맺음말 👋
자바 코딩 테스트에서 정렬은 피할 수 없는 중요한 주제입니다.
Arrays.sort()와 Collections.sort()의 기본 사용법, 그리고 Comparator를 이용한 커스텀 정렬 방법을 완벽히 익히세요.
이 글에서 다룬 내용들만 잘 숙지한다면, 어떤 정렬 문제도 자신 있게 해결할 수 있을 거예요! 꾸준한 연습만이 실력 향상의 지름길입니다. 화이팅! 🎉
궁금한 점이 있다면 언제든지 질문해주세요! 😊
할 수 있다!!!