[JAVA] 프로그래머스 | 42746 가장 큰 수

 

📝 TIL

- [프로그래머스] 42746 가장 큰 수

 

제한사항

numbers의 길이는 1 이상 100,000 이하입니다.

numbers의 원소는 0 이상 1,000 이하입니다.

정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

 

입출력 예

입력#1

[6, 10, 2]

 

출력#1

"6210"

---

🦔 설계 및 시도

처음에 각 숫자를 문자로 바꿔서 비교하면 되지 않나?라고 생각했는데

이 경우에 반례가 있었다

 

예를 들어 [6, 30, 3] 일 경우 문자열 정렬로 비교하면 [6, 30, 3]으로 정렬되는데,
실제는 6303 < 6330 이므로 [6, 3, 30]으로 답이 나와야 한다.

 

따라서 두 수의 합을 비교했어야 했다!

즉 숫자 비교가 아니라 붙였을 때 문자열 크기 비교가 핵심

 

1. 배열을 문자열로 변경하여 배열에 저장

2. 두 문자열의 합을 기준으로 하여 정렬

3. 배열을 join하여 출력(이때 000일 경우 0 출력)

 

더해서 역시나.. Comparator + compareTo 구문이 헷갈렸다

주말에 관련 내용을 정리해서 마스터 해야겠다

 

🔥 풀이에 사용된 개념

- 문자열 정렬 기준: (b+a).compareTo(a+b)

- Arrays.sort() + 람다식 Comparator

 

 

💡 풀이 소스 코드

숫자의 개수 : n, 최대 자리수 : k

 

시간복잡도 : O(n log n * k)

- 정렬 : 비교 시 두 문자열의 길이는 O(k) -> 정확하게 하면 O(n log n * k)

 

공간복잡도 : O(n * k)

 

import java.util.*;
class Solution {
    public String solution(int[] numbers) {
        // 문자열로 배열 저장
        String[] num = new String[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            num[i] = Integer.toString(numbers[i]);
        }
        
        // 순서 비교
        Arrays.sort(num, (a, b) -> (b+a).compareTo(a+b));
        if (num[0].equals("0")) return "0";

        return String.join("", num);
    }
}

 

---

🚀 새로 배운 내용

- 단순 숫자 정렬이 아니라 문자열 붙이기 결과로 정렬 기준을 만들어야 한다

- Arrays.sort()는 안정 정렬이 아니므로 커스텀 comparator가 중요하다

 

---

😺  느낀점

나는 상대적으로 구현에 오래 걸리기에 다양한 문제를 많이 풀어보며 로직을 바로 떠올리게 하는 것이 중요하다!

 

 

*소스 코드는 다음 깃허브에 올라옵니다 - https://github.com/s0ooo0k/Algorithm_Study

GitHub - s0ooo0k/Algorithm_Study: Algorithm Study 문제 및 풀이