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

1. 문제

---

프로그래머스

 

2. 풀이 과정

---

주어진 0또는 양의 정수들을 가지고 조합해서 만들 수 있는 가장 큰 수를 찾으면 되는 문제이다.

 

가장 큰 수를 만들기 위해선 큰 '숫자'가 앞으로 가야한다.

여기서 '숫자'는 그 수 자체가 아니라 0~9까지의 숫자를 말한다. 

예를 들어 3, 10이 있으면 수자체는 10이 크지만 3이 앞으로 가야 더 큰 수를 만들 수 있다.

(310 vs 103) 

 

그렇기 때문에 각 수를 문자열로 변환 후 사전역순으로 정렬하면 될 것 같다.

하지만 한가지 더 주의해야할점이 있다.

3과 30같은 경우이다. 이 경우 단순히 사전역순으로 정렬하면 30 - 3 순으로 정렬된다.

하지만 실제로는 3 - 30이어야 더 큰 수를 만들 수 있다.

 

그러므로 이 문제를 해결하기 위해선 두 수를 순서를 바꿔가며 조합을 해보고 더 큰 수를 택하면 된다.

3, 30의 경우 330이 303보다 크기때문에 3-30 순으로 정렬해야 한다.

 

이제 정리해보겠다.

문제 해결과정은 다음과 같다.

1. 정수 배열을 문자열 배열로 변환한다.

2. 두 수를 조합해서 더 큰 수를 기준으로 내림차순 정렬을 한다.

 

3. 내 코드

---

import java.util.*;
class Solution {
    public String solution(int[] numbers) {
        // numbers 배열을 문자열 배열로 변환
        String[] strArr = new String[numbers.length];
        for(int i = 0; i < strArr.length; i++) {
            strArr[i] = Integer.toString(numbers[i]);
        }
        
        // 두 수를 조합하고 비교하여 더 큰 수를 기준으로 내림차순 정렬
        Arrays.sort(strArr, (s1, s2) -> {
            
            int a = Integer.parseInt(s1 + s2);
            int b = Integer.parseInt(s2 + s1);
            return b - a;
        });
    
        // 정렬된 수를 나열하여 문자열로 만듦
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < strArr.length; i++) {
            sb.append(strArr[i]);
        }
        
        // 정답의 맨 앞이 0인 경우는 0을 반환
        return sb.toString().charAt(0) == '0' ? "0" : sb.toString();
    }
}

시간 복잡도

• O(NlogN)

정수 배열을 문자열 배열로 변환 - O(N)

내림차순 정렬 - O(NlogN)

정렬된 수를 나열하여 문자열로 - O(N)

--> 따라서 시간복잡도는 O(NlogN)이다.