알고리즘 문제를 풀다 보면 데이터를 정렬해야 하는 상황이 발생한다. Java에서는 배열과 스트림(Stream)을 효과적으로 정렬할 수 있는 다양한 방법을 제공한다. 특히 Comparable과 Comparator 인터페이스를 이해하고 활용하는 것이 문제를 푸는데 중요하다. 이 글에서는 알고리즘 문제 풀이에 필수적인 Java의 정렬 방법을 정리하겠다.
1. 배열과 스트림 기본 정렬
배열 정렬 Arrays.sort()
Arrays.sort() 클래스의 sort() 메서드는 배열을 직접 정렬(in-place sort)한다. 기본적으로 오름차순으로 정렬되며, 숫자나 문자열과 같이 이미 순서가 정의된 타입에 바로 사용할 수 있다.
import java.util.Arrays;
int[] numbers = {5, 2, 8, 1, 9};
Arrays.sort(numbers);
// numbers 배열은 이제 {1, 2, 5, 8, 9}가 됩니다.
System.out.println(Arrays.toString(numbers));
String[] fruits = {"Banana", "Apple", "Cherry"};
Arrays.sort(fruits);
// fruits 배열은 이제 {"Apple", "Banana", "Cherry"}가 됩니다.
System.out.println(Arrays.toString(fruits));스트림 (Stream) 정렬 sroted()
java.util.stream.Stream의 sorted() 메서드는 스트림의 요소들을 정렬하여 새로운 스트림을 반환한다. 원본 컬렉션은 변경되지 않는다는 특징이 있다.
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
List<Integer> numberList = Arrays.asList(5, 2, 8, 1, 9);
List<Integer> sortedList = numberList.stream()
.sorted()
.collect(Collectors.toList());
// sortedList는 {1, 2, 5, 8, 9} 입니다.
// numberList는 그대로 {5, 2, 8, 1, 9} 입니다.
System.out.println(sortedList);2. Comparable vs Comparator
사용자 정의 객체(예: Student, Point 클래스)를 정렬하려면 Java에게 어떤 기준으로 정렬해야 할지 알려주어야 한다. 이때 Comparable과 Comparator 인터페이스가 사용된다.
Comparable: 클래스에 내장하는 기본 정렬
Comparable 인터페이스는 정렬할 클래스가 직접 구현한다. CompareTo 메서드를 오버라이드하여 정렬 기준을 정의하며, 이를 자연 순서라고 부른다.
- CompareTo 메서드
- 음수: 현재 객체(this)가 비교 대상(o)보다 앞에 와야 함
- 0: 두 객체의 순서가 같음
- 양수: 현재 객체(this)가 비교 대상(0)보다 뒤에 와야 함
import java.util.Arrays;
class Student implements Comparable<Student> {
String name;
int score;
public Student(String name, int score) {
this.name = name;
this.score = score;
}
@Override
public String toString() {
return name + ": " + score;
}
// 점수 기준 오름차순으로 기본 정렬 기준을 정의
@Override
public int compareTo(Student other) {
// this.score가 other.score보다 작으면 음수, 크면 양수 반환
return this.score - other.score;
}
}
public class Main {
public static void main(String[] args) {
Student[] students = {
new Student("Kim", 90),
new Student("Lee", 85),
new Student("Park", 95)
};
Arrays.sort(students); // Comparable에 정의된 compareTo 메서드를 사용
System.out.println(Arrays.toString(students));
// 출력: [Lee: 85, Kim: 90, Park: 95]
}
}Comparator: 정렬 기준을 외부에서 주입
Comparator 인터페이스는 별도의 클래스를 만들어 구현한다. Compare 매서드를 오버라이드하며, 두 개의 객체를 인자로 받아 비교한다. 이를 통해 원본 클래스를 수정하지 않고도 다양한 정렬 기준을 만들 수 있다.
- Compare 메서드 반환 값의 의미
* 음수: 첫 번째 인자(o1)가 두 번째 인자(o2)보다 앞에 와야 함- 0: 두 객체의 순서가 같음
- 양수: 첫 번째 인자(o1)가 두 번째 인자(o2)보다 뒤에 와야 함
import java.util.Arrays;
import java.util.Comparator;
// Student 클래스는 위 예시와 동일 (Comparable 구현)
// 점수 기준 내림차순 Comparator
class ScoreDesc implements Comparator<Student> {
@Override
public int compare(Student s1, Student s2) {
// s2.score가 s1.score보다 크면 양수 반환 (s1이 뒤로 감)
return s2.score - s1.score;
}
}
public class Main {
public static void main(String[] args) {
Student[] students = {
new Student("Kim", 90),
new Student("Lee", 85),
new Student("Park", 95)
};
Arrays.sort(students, new ScoreDesc()); // Comparator를 인자로 전달
System.out.println(Arrays.toString(students));
// 출력: [Park: 95, Kim: 90, Lee: 85]
}
}람다(Lambda), 익명 구현 객체
매번 Comparator를 위해 새로운 클래스 파일을 만드는 것이 번거롭다면 익명 구현 객체나 람다 표현식을 사용하면 코드를 간결하게 작성할 수 있다.
익명 구현 객체 (Anonymous Inner Class)
이름 없는 클래스를 즉석에서 만들어 사용하는 방법이다
import java.util.Arrays;
import java.util.Comparator;
// Student 클래스는 위 예시와 동일
public class Main {
public static void main(String[] args) {
Student[] students = {
new Student("Kim", 90),
new Student("Lee", 85),
new Student("Park", 95)
};
// 이름 기준 오름차순 정렬
Comparator<Student> nameComparator = new Comparator<Student>() {
@Override
public int compare(Student s1, Student s2) {
return s1.name.compareTo(s2.name);
}
};
Arrays.sort(students, nameComparator);
System.out.println(Arrays.toString(students));
// 출력: [Kim: 90, Lee: 85, Park: 95]
}
}람다 표현식 (Lambda Expression)
Java 8부터 도입된 람다 표현식을 사용하면 더 간결하게 작성할 수 있다. Comparator가 함수형 인터페이스이므로 람다식으로 대체 가능하다.
import java.util.Arrays;
import java.util.Comparator;
// Student 클래스는 위 예시와 동일
public class Main {
public static void main(String[] args) {
Student[] students = {
new Student("Kim", 90),
new Student("Lee", 85),
new Student("Park", 95)
};
// 1. 점수 기준 내림차순 (가장 간결한 형태)
Arrays.sort(students, (s1, s2) -> s2.score - s1.score);
System.out.println(Arrays.toString(students));
// 출력: [Park: 95, Kim: 90, Lee: 85]
// 2. 이름 기준 오름차순
Arrays.sort(students, (s1, s2) -> s1.name.compareTo(s2.name));
System.out.println(Arrays.toString(students));
// 출력: [Kim: 90, Lee: 85, Park: 95]
}
}흥미로웠던 코드 (feat: 객체지향)
import java.util.*;
import java.util.function.IntPredicate;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class Solution {
public int[] solution(int[] answers) {
return new Students().getBestStudents(
Arrays.stream(answers)
.boxed()
.map(Answer::new)
.collect(Collectors.toList()))
.stream()
.mapToInt(i -> i)
.toArray();
}
private static class Students {
private final List<Student> students;
public Students() {
this.students = new ArrayList<>();
this.students.add(Student.of(1, Arrays.asList(1, 2, 3, 4, 5)));
this.students.add(Student.of(2, Arrays.asList(2, 1, 2, 3, 2, 4, 2, 5)));
this.students.add(Student.of(3, Arrays.asList(3, 3, 1, 1, 2, 2, 4, 4, 5, 5)));
}
public List<Integer> getBestStudents(List<Answer> answers) {
return this.students.stream()
.map(student -> student.getResult(answers))
.collect(Collectors.collectingAndThen(Collectors.toList(), Results::new))
.getBestResults().stream()
.map(Result::getStudentId)
.collect(Collectors.toList());
}
}
private static class Student {
private final Integer id;
private final List<Answer> answerPattern;
public Student(Integer id, List<Answer> answerPattern) {
this.id = id;
this.answerPattern = answerPattern;
}
public static Student of(Integer id, List<Integer> answerPattern) {
return new Student(id, answerPattern.stream()
.map(Answer::new)
.collect(Collectors.toList()));
}
public Result getResult(List<Answer> answers) {
Long correctCount = IntStream.range(0, answers.size())
.filter(isCorrect(answers))
.count();
return new Result(this.id, correctCount.intValue());
}
private IntPredicate isCorrect(List<Answer> answers) {
return index -> {
int patternIndex = index % answerPattern.size();
Answer answer = answerPattern.get(patternIndex);
Answer correctAnswer = answers.get(index);
return answer.isCorrect(correctAnswer);
};
}
}
private static class Results {
private final List<Result> results;
public Results(List<Result> results) {
this.results = results;
}
public List<Result> getBestResults() {
Result bestResult = Collections.max(results);
return results.stream()
.filter(result -> result.isCorrectCountEqualTo(bestResult))
.collect(Collectors.toList());
}
}
private static class Result implements Comparable<Result> {
private final Integer studentId;
private final Integer correctCount;
public Result(Integer studentId, Integer correctCount) {
this.studentId = studentId;
this.correctCount = correctCount;
}
public boolean isCorrectCountEqualTo(Result result) {
return this.correctCount.equals(result.correctCount);
}
public Integer getStudentId() {
return studentId;
}
@Override
public int compareTo(Result o) {
return this.correctCount.compareTo(o.correctCount);
}
}
private static class Answer {
private final Integer answer;
public Answer(Integer answer) {
this.answer = answer;
}
public boolean isCorrect(Answer answer) {
return this.answer.equals(answer.answer);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Answer answer1 = (Answer) o;
return Objects.equals(answer, answer1.answer);
}
@Override
public int hashCode() {
return Objects.hash(answer);
}
}
}
우연히 문제를 푸는데 객체지향적으로 접근한 코드를 보았다.
과거 객체지향에 처음 접했을 때 나도 이렇게 방대하게 코드를 작성했었던거 같다.
이전까지 설명했었던 Comparable과 Comparator의 인터페이스 실체화정도가 아닌 로직을 여러 클래스에 나누는 정도의 오버엔지니어링은 알고리즘에 불필요하지 않을까 싶다.
유연할 수록 코드 이해해 문제가 생길 수 있는데 간결하고 직관적이어야하는 알고리즘 문제풀이에 이런 접근은 위험할 수 있다고 생각한다.
공부 내용을 가볍게 적어놓는 블로그.
오타 났어요