TIL_20250306_java문자열 정렬

오늘은 문자열을 내림차순으로 정렬하는 문제를 해결하는 과정에서 겪은 시행착오와 최적의 해결 방법을 정리해보았다.

---

🔍 문제 설명

문자열 s가 주어졌을 때, 문자를 큰 것부터 작은 순서로 정렬하여 새로운 문자열을 반환하는 함수를 작성하라.

• s는 영문 대소문자로만 구성되며, 대문자는 소문자보다 작은 것으로 간주한다.
• 제한 사항: s의 길이는 1 이상이다.

🔹 입출력 예시

입력 (s)	출력 (return)
"Zbcdefg"	"gfedcbZ"

---

⚡ 문제 해결 과정

1️⃣ Arrays.sort()를 이용한 정렬 시도 → 실패

가장 먼저 떠올린 방법은 Arrays.sort()를 이용하여 정렬하는 것이었다.
하지만 Arrays.sort()는 배열을 정렬하는 메서드이므로, 문자열을 정렬하려면 먼저 배열로 변환해야 한다.

그러나 Java에서 String은 char 배열로 직접 변환할 수 없고, String[]으로 변환해야 한다고 착각하여 막혔다.
(→ 사실 toCharArray()를 사용하면 쉽게 char[] 배열로 변환 가능)

2️⃣ String 배열을 활용한 정렬 시도 → 비효율적

다음으로 String을 String[]으로 변환한 후, for문을 사용해 문자 하나하나를 배열에 넣고 정렬하는 방법을 생각했다.

String s = "Zbcdefg";
String[] arr = new String[s.length()];
for (int i = 0; i < s.length(); i++) {
    arr[i] = String.valueOf(s.charAt(i));
}
Arrays.sort(arr, Comparator.reverseOrder());

하지만 이 방법은

• 문자 하나를 저장하기 위해 불필요하게 String 객체를 생성해야 하고,
• 문자열 결합 시 추가적인 연산이 필요하여 비효율적이었다.

Java에서는 char 타입이 기본 자료형(primitive type)이므로, Character[] 대신 char[]을 사용해야 성능이 더 좋다.
따라서 이 방법은 적절하지 않다고 판단하고 다른 방법을 찾았다.

3️⃣ Comparator를 이용한 정렬 시도 → 다시 고민

Arrays.sort()를 사용할 때 내림차순 정렬을 위해 Comparator.reverseOrder()를 사용하려 했지만,
Arrays.sort()는 char[] 배열에서는 Comparator를 지원하지 않음을 알게 되었다.
(Java의 char는 기본 자료형이므로 Comparator를 사용할 수 없음)

char[] arr = s.toCharArray();
Arrays.sort(arr, Comparator.reverseOrder()); // 오류 발생!

이 문제를 해결하기 위해
1. char[]을 Character[]로 변환 후 정렬
2. 정렬 후 StringBuilder.reverse() 활용

두 가지 방법을 고민했고, 최종적으로 StringBuilder.reverse()를 활용하는 방법을 선택했다.

---

✅ 최종 해결 방법: toCharArray() + Arrays.sort() + StringBuilder.reverse()

import java.util.Arrays;

class Solution {
    public String solution(String s) {
        char[] arr = s.toCharArray(); // 문자열을 char 배열로 변환
        Arrays.sort(arr); // 오름차순 정렬 (대문자 먼저 정렬됨)
        return new StringBuilder(new String(arr)).reverse().toString(); // 뒤집어서 반환
    }
}

✔ 해결 과정 정리

1. toCharArray() 를 이용해 문자열을 char[] 배열로 변환
2. Arrays.sort(arr) 를 이용해 오름차순 정렬
   • Java의 기본 정렬 규칙에 따라, 대문자가 소문자보다 작은 값으로 정렬됨 (A-Z → a-z)
3. StringBuilder.reverse() 를 이용해 배열을 뒤집어 내림차순 정렬된 문자열 생성

---

⏳ 시간 복잡도 분석

연산	시간 복잡도
toCharArray()	O(N)
Arrays.sort()	O(N log N)
reverse()	O(N)
총 시간 복잡도	O(N log N)

➡ 정렬 알고리즘의 한계 때문에 최적의 복잡도는 O(N log N) 이다.

---

🎯 정리 & 배운 점

✔ Arrays.sort()를 사용할 때, 기본 자료형인 char 배열은 Comparator를 사용할 수 없다는 점을 인지했다.
✔ StringBuilder.reverse()를 활용하면 간단하게 내림차순 변환이 가능하다는 것을 배웠다.
✔ Java에서 문자열을 다룰 때는 toCharArray()를 활용하여 char[]로 변환하는 것이 성능적으로 유리하다는 점을 확인했다.