파이썬과 다르게 자바는 ArrayList같은것을 사용하지않으면 단순array에선 바로 sort하는 기능이 없고 util 라이브러리를 import해서 사용해야한다. 오늘은 내가 알고리즘 테스트를 준비하는 겸.. 기본 자료구조에 대해 정리해보고자한다.
1. int array 정렬
Arrays.sort()를 사용하지 않는 경우
이 경우 선택정렬의 알고리즘이기때문에 시간복잡도 O(n^2)이다. 이렇게 정렬했다가는 알고리즘테스트에서 폭망한다.
int[] arr = {5, 3, 8, 2, 1, 4};
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 두 원소의 위치를 바꿉니다.
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
Arrays.sort()를 사용하는 코드
Arrays.sort의 경우 퀵소트를 사용하기때문에 시간복잡도가 O(nlogn)이기 때문에 정렬이 필요할땐 무조건 사용해야한다.
int[] arr = {5, 3, 8, 2, 1, 4};
Arrays.sort(arr); // 오름차순 정렬2. int array 역정렬
1번과 같은 단순하게 숫자를 정렬하는 건 쉽다. 이제 역으로 정렬해야되는것부터 조금 헷갈린다. 왜냐면 Arrays.sort의 경우 int[]는 정렬만 지원하고 역정렬부터는 Arrays.sort(array인자, Comparator객체)를 할당해줘야하기때문이다.
그런데 이 Comparator객체를 할당하는게 문제인데 int같은 원시타입은 Comparator를 바로 사용하지 못해서
Integer[]로 바꾼뒤 사용해야한다.
Comparator 인터페이스를 사용하여 역정렬
이 경우 compare(반환함수)의 결과값에 따라 정렬 대상인 a와 b를 어떻게 정렬할지 다르게 취급한다.
- 반환 값이 양수일 경우, sort 메소드는 a가 b보다 "더 작다"고 판단하고 두 요소의 순서를 바꾼다.
- 반환 값이 음수일 경우, sort 메소드는 a가 b보다 "더 크다"고 판단하고 두 요소의 순서를 유지한다.
- 반환 값이 0일 경우, 두 요소는 같다고 간주되어 순서가 변경되지 않는다.
int[] arr = {5, 3, 8, 2, 1, 4}; Integer[] integerArr = new Integer[arr.length]; for (int i = 0; i < arr.length; i++) { integerArr[i] = arr[i]; } Arrays.sort(integerArr, new Comparator<Integer>() { public int compare(Integer a, Integer b) { return b - a; } });
위 코드의 경우 람다함수로도 간결하게 표현이 가능하다.
Arrays.sort(arr, (a, b) -> b - a);
Collections의 reverseOrder()를 사용하기
위의 경우 비교함수를 직접 구현하는 셈이다. 그런데 직접 구현할 필요없이 Collections에서 제공하는 메소드를 작성하면 위와 똑같이 동작한다.
Integer[] arr = {5, 3, 8, 2, 1, 4};
Arrays.sort(arr, Collections.reverseOrder());reverseOrder() 메소드의 내부코드를 보면 이렇게 Comparator 객체를 반환하고있다.
public static <T> Comparator<T> reverseOrder() {
return (Comparator<T>) ReverseComparator.REVERSE_ORDER;
}3. String array정렬
기본 정렬
String[] arr = {"banana", "apple", "cherry"};
Arrays.sort(arr);역정렬
String[] arr = {"banana", "apple", "cherry"};
Arrays.sort(arr, (a, b) -> Integer.compare(a.length(), b.length()));메소드를 사용한 역정렬
String[] arr = {"banana", "apple", "cherry"};
Arrays.sort(arr, Collections.reverseOrder());().compareTo()
compareTo는 문자열인 a와 b를 비교할때 사용한다.
String a = "apple";
String b = "banana";
int result = a.compareTo(b); // a < b 이므로 음수를 반환혹은 이런식의 활용도 가능하다.
Arrays.sort(integerNumbers, (a, b) -> {
String numA = Integer.toString(a);
String numB = Integer.toString(b);
return (numB+numA).compareTo(numA+numB);
});compareTo는 어떻게 동작할까? compareTo는 반환값이 0,음수,양수이느냐에 따라 정렬 결과가 바뀐다.
- 반환 값이 0: 객체 a와 b는 동등합니다.
- 반환 값이 양수: 객체 a가 b보다 큽니다 (또는 a가 b 뒤에 옵니다).
- 반환 값이 음수: 객체 a가 b보다 작습니다 (또는 a가 b 앞에 옵니다).
그런데 String도 Comparator객체를 사용할수 있는데 int는 왜안될까?
밑에서 나올 다차원 배열에도 해당되는 말이지만 String[] 배열은 객체 배열이기때문에 Comparator를 사용할 수 있지만, int[] 배열은 기본 타입 배열이므로 Comparator를 사용할 수 없다.
4. 다차원 배열 정렬
0번째 요소를 기준으로 정렬
다차원 배열의 경우 정렬의 기준점이 중요하다.
int[][] arr = {{3, 2}, {1, 5}, {4, 1}};
Arrays.sort(arr, (a, b) -> Integer.compare(a[0], b[0]));
1번째 요소를 기준으로 정렬
int[][] arr = {{3, 2}, {1, 5}, {4, 1}};
Arrays.sort(arr, (a, b) -> Integer.compare(a[1], b[1]));
0번째 요소를 기준으로 역순 정렬
int[][] arr = {{3, 2}, {1, 5}, {4, 1}};
Arrays.sort(arr, (a, b) -> Integer.compare(b[0], a[0]));
그런데 int[][]인데도 Integer.compare로 정렬해도 된다면 int[]도 Integer.compare를 사용해서 정렬하면 되는 거 아닐까?
이때 알아야할점은 int[], int[][]는 둘다 객체이지만 int[]에서 각각의 array에 들어가는 int는 기본타입이며 int[][]에서 각각의 array에 들어가는 int[]는 객체이기에 int[][]는 객체 배열이기에 Integer.compare를 사용할 수 있는 것이다.
5. 람다 함수
그런데 같은 정렬임에도 다양한 방식으로 정렬이 가능한데 도대체 각자 무슨차이인걸까?
// 1번 방식
Arrays.sort(arr, new Comparator<Integer>() {
public int compare(Integer a, Integer b) {
return b - a;
}
});// 2번 방식
Arrays.sort(arr, (a, b) -> {
return b - a;
});// 3번 방식
Arrays.sort(arr, (a, b) -> Integer.compare(a,b));// 4번 방식
Arrays.sort(arr, (a, b) -> a.compareTo(b));2번 방식의 경우 1번 방식을 람다함수로 작성한것이다. 두개는 같은코드라고 볼 수 있다. 1번 방식의 경우 Comparator 인터페이스를 익명 클래스로 구현하는데 이 경우 번거로우니 람다 표현식으로 기존 코드를 구현을 단순화했다고보면 된다.
그렇다면 2번방식과 3번 방식은 뭐가 다를까? 둘다 똑같이 동작하지만 만약 큰 정수값에서는 오버플로 문제를 야기하기도 한다. 예를 들어 a가 매우 작고 b가 매우 클 경우 b-a 계산은 정수범위를 초과하여 잘못된 값을 출력하기도 한다는 것이다.
안전성과 정확성 측면에서는 Integer.compare 메소드를 사용하는 것이 좋다고한다.
또한 3번과 4번 방식의 경우 Integer.compare(a,b)는 두개의 int값을 비교하는 반면 a.compareTo(b)는 Integer객체를 비교할 때 사용된다. Integer.compare(a,b)의 경우 내부동작에서 int값으로 변환되어 비교되기에 int와 Integer일때 구분해서 둘을 사용하는 게 좋다.
추가. 인터페이스를 익명 클래스로 구현한다는 것은 무엇일까?
인터페이스를 익명 클래스로 구현한다는 말은 Java에서 인터페이스의 구현을 이름이 없는 클래스(익명 클래스)를 사용해 직접 정의하는 걸 말한다.
익명 클래스는 클래스 선언과 객체 생성을 동시에 수행하는 일회용 클래스이며 해당 로직에서만 사용되는 경우 사용한다.
Comparator<Integer> myComparator = new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
// 비교 로직 구현
return a - b;
}
};이 코드에서 new Comparator<>(){ ~ } 부분이 익명 클래스이다. Comparator<Integer> 인터페이스의 compare 메소드를 오버라이드 구현하고 있으며 이 익명클래스의 인스턴스는 myComparator변수에 할당된다.
그러나 이러한 방식은 Java8이전까지 사용되었으며, Java8이후로는 람다 표현식의 도입으로 간결하게 작성할 수 있게됐다.
댓글