정렬, Arrays.sort부터 Comparator까지 한 번에 정리하기

정렬 알고리즘

Arrays.sort, Comparator, 문자열 정렬, 원본 배열 보존까지

코딩테스트 문제를 풀다 보면 정렬은 정말 자주 등장한다.

처음에는 정렬을 단순히 숫자를 오름차순이나 내림차순으로 나열하는 기능 정도로 생각했다.
하지만 문제를 풀다 보니 정렬은 단순한 문법이 아니라, 데이터를 문제 풀이에 유리한 순서로 재배치하는 과정이라는 생각이 들었다.

예를 들어 K번째 수를 찾거나, 구간이 겹치는지 확인하거나, 가장 큰 수를 만들거나, 좌표를 압축하는 문제에서도 정렬이 핵심으로 사용된다.

이번 글에서는 Java 기준으로 정렬의 기본 문법과 코딩테스트에서 자주 나오는 정렬 유형을 정리해보려고 한다.

---

1. 정렬이란?

정렬은 데이터를 특정 기준에 따라 순서대로 배치하는 것이다.

가장 기본적인 정렬은 오름차순 정렬이다.

int[] arr = {5, 2, 4, 1, 3};

Arrays.sort(arr);

System.out.println(Arrays.toString(arr));

결과는 다음과 같다.

[1, 2, 3, 4, 5]

반대로 큰 값부터 작은 값 순서로 나열하면 내림차순 정렬이다.

[5, 4, 3, 2, 1]

코딩테스트에서 중요한 것은 단순히 정렬 메서드를 외우는 것이 아니라,
어떤 기준으로 정렬해야 문제를 쉽게 풀 수 있는지 판단하는 것이다.

---

2. Java 정렬 기본 문법 한눈에 보기

데이터 형태	오름차순 정렬	내림차순 정렬
int[]	Arrays.sort(arr)	오름차순 정렬 후 뒤에서부터 사용 또는 직접 reverse
Integer[]	Arrays.sort(arr)	Arrays.sort(arr, Collections.reverseOrder())
char[]	Arrays.sort(arr)	오름차순 정렬 후 뒤에서부터 사용
Character[]	Arrays.sort(arr)	Arrays.sort(arr, Collections.reverseOrder())
String[]	Arrays.sort(arr)	Arrays.sort(arr, Collections.reverseOrder())
List<Integer>	Collections.sort(list) 또는 list.sort(null)	list.sort(Collections.reverseOrder())
List<String>	Collections.sort(list)	list.sort(Collections.reverseOrder())
int[][]	Arrays.sort(arr, Comparator)	Arrays.sort(arr, Comparator)

---

3. 기본형 배열과 객체 배열의 차이

Java에서 int[], long[], char[] 같은 기본형 배열은 Arrays.sort()로 정렬할 수 있다.

int[] arr = {5, 2, 4, 1, 3};

Arrays.sort(arr);

System.out.println(Arrays.toString(arr));

결과:

[1, 2, 3, 4, 5]

기본 정렬은 오름차순이다.

다만 int[]는 기본형 배열이라서 아래처럼 Collections.reverseOrder()를 바로 사용할 수 없다.

int[] arr = {5, 2, 4, 1, 3};

// 불가능
Arrays.sort(arr, Collections.reverseOrder());

Collections.reverseOrder()는 Integer[], String[]처럼 객체 배열에서 사용할 수 있다.

---

4. int[]를 내림차순 정렬하는 방법

처음에는 int[]를 내림차순 정렬하려면 무조건 Integer[]로 바꿔야 하는지 궁금했다.

결론부터 말하면 꼭 바꿔야 하는 것은 아니다.

방법 1. 오름차순 정렬 후 뒤에서부터 사용하기

코딩테스트에서는 이 방법이 가장 간단하다.

int[] arr = {5, 2, 4, 1, 3};

Arrays.sort(arr);

for (int i = arr.length - 1; i >= 0; i--) {
    System.out.print(arr[i] + " ");
}

출력:

5 4 3 2 1

배열 자체를 내림차순으로 바꾸는 것은 아니지만, 큰 값부터 사용해야 하는 경우에는 충분하다.

방법 2. 오름차순 정렬 후 직접 뒤집기

배열 자체를 내림차순 상태로 만들고 싶다면 정렬 후 앞뒤 값을 교환하면 된다.

int[] arr = {5, 2, 4, 1, 3};

Arrays.sort(arr);

int left = 0;
int right = arr.length - 1;

while (left < right) {
    int temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;

    left++;
    right--;
}

System.out.println(Arrays.toString(arr));

결과:

[5, 4, 3, 2, 1]

방법 3. Integer[]로 변환해서 내림차순 정렬하기

Comparator나 Collections.reverseOrder()를 사용하고 싶다면 Integer[]로 바꾸면 된다.

int[] arr = {5, 2, 4, 1, 3};

Integer[] boxed = new Integer[arr.length];

for (int i = 0; i < arr.length; i++) {
    boxed[i] = arr[i];
}

Arrays.sort(boxed, Collections.reverseOrder());

System.out.println(Arrays.toString(boxed));

결과:

[5, 4, 3, 2, 1]

Stream을 사용할 수도 있다.

Integer[] boxed = Arrays.stream(arr)
        .boxed()
        .toArray(Integer[]::new);

Arrays.sort(boxed, Collections.reverseOrder());

다만 코딩테스트에서는 Stream이 익숙하지 않다면 굳이 사용하지 않아도 될 것 같다.

---

5. 문자열 정렬은 어떤 기준으로 정렬될까?

문자열 배열은 기본적으로 사전순으로 정렬된다.

String[] words = {"banana", "apple", "carrot"};

Arrays.sort(words);

System.out.println(Arrays.toString(words));

결과:

[apple, banana, carrot]

여기서 처음에 헷갈렸던 부분이 있다.

apple, banana가 정렬되는 것이 배열의 첫 번째 원소 기준 정렬인가? 라는 점이었다.

정확히 말하면 그렇지 않다.

문자열 배열에서 기본 정렬은 배열의 첫 번째 원소만 보는 것이 아니라,
문자열끼리 사전순으로 비교하는 것이다.

즉 "apple"과 "banana"를 비교할 때는 문자열 안의 문자를 앞에서부터 비교한다.

apple
banana

첫 번째 문자부터 비교한다.

a < b

그래서 "apple"이 "banana"보다 앞에 온다.

문자열 기본 정렬은 다음처럼 이해하면 된다.

첫 번째 문자 비교
같으면 두 번째 문자 비교
같으면 세 번째 문자 비교
...

---

6. 문자열 정렬 기준 정리

정렬 기준	코드
사전순 오름차순	Arrays.sort(words)
사전순 내림차순	Arrays.sort(words, Collections.reverseOrder())
문자열 길이 오름차순	Arrays.sort(words, (a, b) -> Integer.compare(a.length(), b.length()))
문자열 길이 내림차순	Arrays.sort(words, (a, b) -> Integer.compare(b.length(), a.length()))
첫 번째 문자 기준 오름차순	Arrays.sort(words, (a, b) -> Character.compare(a.charAt(0), b.charAt(0)))
첫 번째 문자 기준 내림차순	Arrays.sort(words, (a, b) -> Character.compare(b.charAt(0), a.charAt(0)))
두 번째 문자 기준 오름차순	Arrays.sort(words, (a, b) -> Character.compare(a.charAt(1), b.charAt(1)))
두 번째 문자 기준 내림차순	Arrays.sort(words, (a, b) -> Character.compare(b.charAt(1), a.charAt(1)))

---

7. Comparator를 이용한 문자열 정렬

문자열은 기본적으로 사전순으로 정렬되지만, Comparator를 사용하면 원하는 기준을 직접 정할 수 있다.

예를 들어 다음과 같은 문자열 배열이 있다고 하자.

String[] words = {"cat", "car", "banana", "boat", "apple"};

---

7-1. 첫 번째 문자 기준으로 정렬하기

문자열의 첫 번째 문자만 기준으로 정렬하려면 다음과 같이 작성할 수 있다.

Arrays.sort(words, (a, b) -> Character.compare(a.charAt(0), b.charAt(0)));

각 문자열의 첫 번째 문자는 다음과 같다.

문자열	첫 번째 문자
cat	c
car	c
banana	b
boat	b
apple	a

정렬 결과는 다음과 같다.

[apple, banana, boat, cat, car]

이 코드는 첫 번째 문자만 비교한다.
따라서 첫 번째 문자가 같은 문자열끼리는 원래 순서가 유지될 수 있다.

---

7-2. 첫 번째 문자가 같으면 사전순으로 정렬하기

첫 번째 문자가 같을 때는 문자열 전체를 기준으로 사전순 정렬하고 싶다면 보조 기준을 추가하면 된다.

String[] words = {"cat", "car", "banana", "boat", "apple"};

Arrays.sort(words, (a, b) -> {
    int firstCompare = Character.compare(a.charAt(0), b.charAt(0));

    if (firstCompare == 0) {
        return a.compareTo(b);
    }

    return firstCompare;
});

System.out.println(Arrays.toString(words));

결과:

[apple, banana, boat, car, cat]

여기서 핵심은 이 부분이다.

return a.compareTo(b);

String의 compareTo()는 문자열 전체를 사전순으로 비교한다.

예를 들어 "car"와 "cat"을 비교하면, 첫 번째 문자 c, 두 번째 문자 a까지는 같다.
그다음 세 번째 문자를 비교한다.

r < t

그래서 "car"가 "cat"보다 앞에 온다.

---

7-3. 두 번째 문자 기준으로 정렬하기

이번에는 문자열의 두 번째 문자, 즉 인덱스 1을 기준으로 정렬해보자.

String[] words = {"banana", "apple", "kiwi", "carrot"};

Arrays.sort(words, (a, b) -> Character.compare(a.charAt(1), b.charAt(1)));

System.out.println(Arrays.toString(words));

각 문자열의 두 번째 문자는 다음과 같다.

문자열	두 번째 문자
banana	a
apple	p
kiwi	i
carrot	a

두 번째 문자 기준으로 오름차순 정렬하면 다음과 같다.

[banana, carrot, kiwi, apple]

---

7-4. 두 번째 문자가 같으면 사전순으로 정렬하기

두 번째 문자가 같은 경우에도 사전순으로 정렬하고 싶다면 보조 기준을 추가하면 된다.

String[] words = {"carrot", "banana", "apple", "kiwi", "cat"};

Arrays.sort(words, (a, b) -> {
    int secondCompare = Character.compare(a.charAt(1), b.charAt(1));

    if (secondCompare == 0) {
        return a.compareTo(b);
    }

    return secondCompare;
});

System.out.println(Arrays.toString(words));

두 번째 문자가 a인 문자열들은 다음과 같다.

carrot
banana
cat

이 문자열들을 사전순으로 정렬하면 다음과 같다.

banana
carrot
cat

전체 결과는 다음과 같다.

[banana, carrot, cat, kiwi, apple]

이처럼 Comparator는 기준을 여러 단계로 나누어 정렬할 수 있다.

1차 기준: 두 번째 문자 기준 오름차순
2차 기준: 두 번째 문자가 같으면 문자열 전체 사전순

주의할 점은 문자열 길이가 짧은 경우이다.

String[] words = {"a", "banana", "apple"};

이런 경우 "a"는 두 번째 문자가 없기 때문에 charAt(1)을 사용하면 오류가 발생할 수 있다.

---

8. 2차원 배열에서 원하는 기준으로 정렬하기

코딩테스트에서는 단순 오름차순 정렬보다 내가 원하는 기준으로 정렬하는 문제가 더 자주 나온다.

예를 들어 2차원 배열이 있을 때:

int[][] arr = {
    {3, 4},
    {1, 2},
    {2, 5}
};

첫 번째 원소 기준으로 오름차순 정렬하려면 다음과 같이 작성한다.

Arrays.sort(arr, (a, b) -> Integer.compare(a[0], b[0]));

두 번째 원소 기준으로 오름차순 정렬하려면 다음과 같이 작성한다.

Arrays.sort(arr, (a, b) -> Integer.compare(a[1], b[1]));

두 번째 원소 기준으로 내림차순 정렬하려면 비교 순서를 반대로 작성한다.

Arrays.sort(arr, (a, b) -> Integer.compare(b[1], a[1]));

여기서 중요한 점은 모든 배열에서 두 번째 원소 기준 정렬이 가능한 것은 아니라는 것이다.

예를 들어 int[]는 각 원소가 숫자 하나이다.

int[] arr = {5, 2, 8, 1};

이 배열의 각 원소는 다음과 같다.

5
2
8
1

각 원소가 숫자 하나이기 때문에 “각 원소의 두 번째 값”이라는 개념이 없다.
따라서 int[]에서는 두 번째 원소 기준 정렬이라는 표현이 맞지 않는다.

반면 int[][]는 각 원소가 배열이다.

int[][] arr = {
    {1, 5},
    {2, 3},
    {3, 8}
};

각 원소는 다음과 같다.

{1, 5}
{2, 3}
{3, 8}

이 경우에는 각 원소 안에 0번째 값, 1번째 값이 있으므로 두 번째 원소 기준 정렬이 가능하다.

---

9. 타입별 원하는 기준 정렬 가능 여부

타입	원하는 기준 정렬 가능 여부	예시
int[]	제한적	값 자체 기준으로만 정렬 가능
Integer[]	가능	숫자값 기준 오름차순/내림차순
char[]	제한적	문자값 기준으로만 정렬 가능
Character[]	가능	문자 기준 오름차순/내림차순
String[]	가능	사전순, 길이순, 특정 문자 기준 등
int[][]	가능	첫 번째 값, 두 번째 값 기준 정렬
객체 배열	가능	객체의 특정 필드 기준 정렬
List<Integer>	가능	숫자값 기준 오름차순/내림차순
List<String>	가능	사전순, 길이순, 특정 문자 기준

---

10. Comparator에서 뺄셈 비교를 조심해야 하는 이유

Comparator를 사용할 때 다음과 같은 코드를 자주 볼 수 있다.

Arrays.sort(arr, (a, b) -> a - b);

2차원 배열에서는 이런 코드도 자주 보인다.

Arrays.sort(arr, (a, b) -> a[0] - b[0]);

작은 숫자를 비교할 때는 문제가 없어 보인다.

int a = 3;
int b = 5;

System.out.println(a - b); // -2

a - b가 음수이면 a가 앞에 오고, 양수이면 b가 앞에 온다.
그래서 정렬 기준으로 사용할 수 있다.

하지만 숫자의 범위가 아주 크면 문제가 생길 수 있다.

Java의 int는 표현할 수 있는 범위가 정해져 있다.

int 최소값: -2,147,483,648
int 최대값:  2,147,483,647

예를 들어 다음과 같은 두 값이 있다고 해보자.

int a = -2_000_000_000;
int b =  2_000_000_000;

정상적인 수학 계산이라면:

a - b
= -2,000,000,000 - 2,000,000,000
= -4,000,000,000

결과는 -4,000,000,000이다.

그런데 int는 -4,000,000,000을 표현할 수 없다.
그래서 오버플로우가 발생해 예상과 다른 값이 나올 수 있다.

int a = -2_000_000_000;
int b =  2_000_000_000;

System.out.println(a - b);

출력 결과는 예상과 다르게 양수가 나올 수 있다.

294967296

원래는 음수가 나와야 하는데 양수가 나온 것이다.

---

11. Comparator에서는 왜 오버플로우가 문제가 될까?

Comparator는 반환값의 부호를 보고 정렬 순서를 판단한다.

반환값	의미
음수	a가 b보다 앞에 온다
0	순서가 같다
양수	a가 b보다 뒤에 온다

오름차순 정렬에서 아래 코드를 사용한다고 해보자.

(a, b) -> a - b

계산 결과	의미
a - b < 0	a가 더 작으므로 앞에 온다
a - b == 0	두 값이 같다
a - b > 0	a가 더 크므로 뒤에 온다

그런데 오버플로우가 발생하면 실제 비교 결과와 반대되는 부호가 나올 수 있다.

예를 들어:

int a = -2_000_000_000;
int b =  2_000_000_000;

실제로는 a가 더 작다.

-2,000,000,000 < 2,000,000,000

따라서 오름차순에서는 a가 b보다 앞에 와야 한다.

하지만 a - b 결과가 오버플로우로 양수가 되면 Comparator는 이렇게 판단한다.

a - b > 0

즉, a가 b보다 크다고 잘못 판단한다.
그래서 정렬 결과가 틀어질 수 있다.

---

12. 안전한 비교 방법: Integer.compare()

이 문제를 피하려면 Integer.compare()를 사용하면 된다.

Arrays.sort(arr, (a, b) -> Integer.compare(a, b));

Integer.compare(a, b)는 단순히 a - b를 계산하는 방식이 아니라, 두 값을 직접 비교해서 결과를 반환한다.

개념적으로는 이런 방식에 가깝다.

if (a < b) {
    return -1;
} else if (a == b) {
    return 0;
} else {
    return 1;
}

그래서 a - b처럼 계산 결과가 int 범위를 넘어가는 문제가 생기지 않는다.

정리하면 다음과 같다.

정렬 기준	안전한 코드
숫자 오름차순	Integer.compare(a, b)
숫자 내림차순	Integer.compare(b, a)
첫 번째 원소 오름차순	Integer.compare(a[0], b[0])
첫 번째 원소 내림차순	Integer.compare(b[0], a[0])
두 번째 원소 오름차순	Integer.compare(a[1], b[1])
두 번째 원소 내림차순	Integer.compare(b[1], a[1])
long 타입 비교	Long.compare(a, b)

단순한 문제에서는 a - b도 동작할 수 있지만, 실전에서는 Integer.compare()를 사용하는 편이 더 안전하다.

---

13. 정렬의 시간복잡도

Java의 Arrays.sort()는 보통 O(N log N)의 시간복잡도를 가진다.

코딩테스트에서 입력 크기가 크면 완전탐색으로는 풀 수 없는 경우가 많다.

예를 들어 데이터 개수가 100,000개라면 모든 쌍을 비교하는 O(N²) 풀이는 부담스럽다.

100,000 × 100,000 = 10,000,000,000

이런 경우 정렬을 사용해서 문제를 O(N log N) 또는 O(N log N + N) 정도로 줄일 수 있는지 생각해봐야 한다.

정렬 문제를 볼 때는 단순히 “정렬하면 되겠네”가 아니라,
정렬 후에 한 번 순회하면서 답을 구할 수 있는지도 같이 확인해야 한다.

---

14. 코딩테스트에서 자주 나오는 정렬 문제 유형

정렬은 여러 유형의 문제에서 활용된다.
내가 앞으로 연습할 문제들을 기준으로 정리하면 크게 다음과 같다.

유형	핵심 아이디어	대표 문제
K번째 수 찾기	배열 일부를 자르고 정렬 후 k번째 값 찾기	프로그래머스 K번째수
Comparator 기준 정렬	문제 조건에 맞게 직접 정렬 기준 만들기	프로그래머스 가장 큰 수
정렬 후 조건 찾기	정렬된 상태에서 조건을 만족하는 값 탐색	프로그래머스 H-Index
중복 제거	정렬 후 인접한 값 비교	코딜리티 Distinct
구간 정렬	시작점 또는 끝점 기준으로 구간 정렬	프로그래머스 요격 시스템, 단속카메라
좌표 압축	값의 크기 대신 순위를 부여	백준 좌표 압축
정렬 + 그리디	정렬 후 현재 선택이 최선이 되도록 처리	단속카메라, 요격 시스템
정렬 + 투포인터	정렬 후 양쪽 포인터로 조건 탐색	두 수의 합 유형

---

15. K번째 수 찾기 유형

가장 기본적인 정렬 활용 문제다.

배열의 일부를 자르고, 정렬한 뒤, 원하는 위치의 값을 찾는다.

문제 흐름은 다음과 같다.

1. 배열의 특정 구간을 자른다.
2. 자른 배열을 정렬한다.
3. k번째 값을 반환한다.

Java에서는 Arrays.copyOfRange()를 사용하면 배열을 쉽게 자를 수 있다.

int[] sliced = Arrays.copyOfRange(array, start, end);

Arrays.sort(sliced);

여기서 주의할 점은 copyOfRange(array, start, end)에서 end는 포함되지 않는다는 것이다.

예를 들어 문제에서 2번째부터 5번째까지 자르고 싶다면:

Arrays.copyOfRange(array, 1, 5);

실제로 가져오는 인덱스는 다음과 같다.

1, 2, 3, 4

문제 기준으로는 2번째부터 5번째까지가 맞다.

---

16. 원본 배열을 보존해야 하는 이유

K번째 수 문제를 풀면서 가장 크게 배운 부분은 원본 배열을 보존해야 한다는 점이었다.

처음에는 아래처럼 작성했다.

array = Arrays.copyOfRange(array, i, j + 1);
Arrays.sort(array);
result[indx] = array[k];

이 코드는 잘라낸 배열을 다시 array 변수에 대입한다.

즉, 처음에는 array가 원본 배열을 가리키고 있었지만, 반복문이 한 번 실행된 뒤에는 잘라낸 배열을 가리키게 된다.

예를 들어 원본 배열이 다음과 같다고 하자.

[1, 5, 2, 6, 3, 7, 4]

첫 번째 command에서 2번째부터 5번째까지 자르면:

[5, 2, 6, 3]

그런데 이 값을 다시 array에 대입하면, 다음 command부터는 원본 배열이 아니라 [5, 2, 6, 3]을 기준으로 다시 자르게 된다.

그래서 결과가 꼬일 수 있다.

정확히 말하면 원본 배열의 값이 직접 바뀐 것이라기보다는,
array라는 변수가 원본 배열 참조를 잃고 새 배열을 가리키게 된 것이다.

올바른 방식은 다음과 같다.

int[] sliced = Arrays.copyOfRange(array, i, j + 1);

Arrays.sort(sliced);

result[indx] = sliced[k];

원본 배열은 그대로 두고, 잘라낸 복사본만 정렬해야 한다.

방식	코드	설명	결과
잘못된 방식	array = Arrays.copyOfRange(array, i, j + 1)	array 변수가 잘라낸 배열을 다시 가리킴	다음 반복에서 원본 기준이 깨질 수 있음
올바른 방식	int[] sliced = Arrays.copyOfRange(array, i, j + 1)	원본 배열은 그대로 두고 복사본만 사용	매번 원본 기준으로 처리 가능

---

17. 구간 정렬 문제

구간 정렬은 코딩테스트에서 자주 나오는 유형이다.

예를 들어 다음과 같은 구간들이 있다고 하자.

[1, 5]
[2, 6]
[7, 9]

이런 문제에서는 보통 시작점이나 끝점을 기준으로 정렬한다.

상황	주로 사용하는 정렬 기준
구간을 순서대로 확인해야 할 때	시작점 기준 정렬
겹치는 구간을 병합할 때	시작점 기준 정렬
최소 개수로 구간을 커버해야 할 때	끝점 기준 정렬
가장 빨리 끝나는 구간부터 선택해야 할 때	끝점 기준 정렬

시작점 기준 정렬:

Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

끝점 기준 정렬:

Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

대표 문제로는 프로그래머스 요격 시스템, 단속카메라 등이 있다.

---

18. 좌표 압축 문제

좌표 압축은 값의 크기 자체보다 값의 상대적인 순서가 중요할 때 사용한다.

예를 들어 다음 배열이 있다고 하자.

[1000, 500, 1000, -10]

정렬 후 중복을 제거하면:

[-10, 500, 1000]

각 값에 순위를 매기면 다음과 같다.

-10   → 0
500   → 1
1000  → 2

그러면 원래 배열은 이렇게 바꿀 수 있다.

[1000, 500, 1000, -10]
→ [2, 1, 2, 0]

Java에서는 보통 다음 흐름으로 푼다.

1. 원본 배열을 복사한다.
2. 복사한 배열을 정렬한다.
3. 중복을 제거하면서 순위를 매긴다.
4. 원본 배열의 값을 순위로 변환한다.

예시 코드는 다음과 같다.

int[] arr = {1000, 500, 1000, -10};

int[] sorted = arr.clone();
Arrays.sort(sorted);

Map<Integer, Integer> map = new HashMap<>();

int rank = 0;

for (int num : sorted) {
    if (!map.containsKey(num)) {
        map.put(num, rank++);
    }
}

for (int num : arr) {
    System.out.print(map.get(num) + " ");
}

좌표 압축에서도 중요한 것은 원본 배열을 보존하는 것이다.
정렬은 복사한 배열에서 하고, 결과를 만들 때 원본 값을 기준으로 변환한다.

---

19. 정렬 문제를 풀 때 먼저 생각할 것

정렬 문제를 만나면 바로 코드를 작성하기보다, 먼저 아래 질문을 해보는 것이 좋다.

체크 질문	이유
어떤 값을 기준으로 정렬해야 할까?	문제 풀이 방향이 정렬 기준에서 결정됨
오름차순인가, 내림차순인가?	탐색 방향과 결과가 달라짐
기준이 같을 때는 어떻게 처리할까?	보조 정렬 기준이 필요한 경우가 있음
정렬 후 앞에서부터 볼까, 뒤에서부터 볼까?	최솟값/최댓값 활용 방식이 달라짐
원본 배열을 보존해야 할까?	정렬이나 대입으로 원본 기준이 깨질 수 있음
구간 문제라면 시작점 기준인가, 끝점 기준인가?	그리디 풀이의 핵심이 되는 경우가 많음
기본형 배열인가 객체 배열인가?	Comparator 사용 가능 여부가 달라짐
Comparator에서 뺄셈 비교를 사용해도 안전할까?	값의 범위가 클 경우 오버플로우가 발생할 수 있음

---

20. 정렬 관련 자주 헷갈린 내용 정리

헷갈린 내용	정리
문자열 정렬은 첫 번째 원소 기준인가?	아니다. 문자열끼리 사전순으로 비교한다. 첫 문자부터 차례대로 비교한다.
문자열의 두 번째 문자 기준 정렬은 어떻게 하나?	charAt(1)과 Character.compare()를 사용한다.
문자열의 첫 번째 문자가 같을 때 사전순 정렬은 어떻게 하나?	if (result == 0) return a.compareTo(b);를 보조 기준으로 추가한다.
문자열의 두 번째 문자가 같을 때 사전순 정렬은 어떻게 하나?	두 번째 문자 비교 결과가 0이면 a.compareTo(b)로 비교한다.
int[]도 Comparator를 쓸 수 있나?	기본형 배열이라 직접 사용할 수 없다.
int[] 내림차순은 꼭 Integer[]로 바꿔야 하나?	아니다. 오름차순 정렬 후 뒤에서부터 사용하거나 직접 reverse 해도 된다.
Integer[]는 내림차순 정렬이 가능한가?	가능하다. Collections.reverseOrder()를 사용할 수 있다.
두 번째 원소 기준 정렬은 언제 가능한가?	각 원소가 배열이나 객체처럼 내부 값을 가지고 있을 때 가능하다.
copyOfRange()의 end는 포함되나?	포함되지 않는다. start는 포함, end는 미포함이다.
K번째 수에서 원본 배열을 재사용하면 왜 문제가 되나?	array 변수에 잘라낸 배열을 다시 대입하면 다음 반복에서 원본 기준이 깨진다.
정렬하면 원본 배열이 바뀌나?	Arrays.sort(array)는 해당 배열 자체의 순서를 바꾼다.
원본을 보존하려면?	clone() 또는 copyOfRange()로 복사본을 만들어 정렬한다.
Comparator에서 a - b를 쓰면 왜 위험한가?	두 값의 차이가 int 범위를 벗어나면 오버플로우로 부호가 바뀔 수 있다.
안전한 Comparator 비교 방법은?	Integer.compare(a, b) 또는 Long.compare(a, b)를 사용한다.

---

정리

정렬은 단순히 데이터를 순서대로 나열하는 기능이 아니라,
문제를 풀기 쉽게 데이터의 순서를 재구성하는 과정이다.

이번에 공부하면서 정렬 문제에서 중요하게 봐야 할 부분은 다음과 같다고 느꼈다.

정렬 기준을 어떻게 잡을 것인가
원본 배열을 보존해야 하는가
정렬 후 어떤 방식으로 탐색할 것인가
구간 문제라면 시작점과 끝점 중 무엇을 기준으로 볼 것인가
기본형 배열과 객체 배열의 차이를 알고 있는가
Comparator에서 뺄셈 비교를 사용할 때 오버플로우 위험은 없는가

특히 Java에서는 Arrays.sort(), Arrays.copyOfRange(), Comparator, Integer.compare(), String.compareTo()를 잘 사용할 수 있어야 한다.

정렬 문제는 단순히 오름차순, 내림차순을 적용하는 문제가 아니라,
문제에서 요구하는 기준을 찾아 데이터를 다시 배치하는 문제에 가깝다.

다음에는 이 내용을 바탕으로 프로그래머스 K번째수 문제를 직접 풀어본 기록을 정리해보려고 한다.