가장 큰 수

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

 

입출력 예

 

numbers	return
[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

 

---

푸는 방법 생각

문제를 보고 순열과 정렬 두가지 방법 중 고민했다. 재귀적으로 구현해서 순열로 풀 수 있지만 정렬로 통한 방법이 더 간편하다고 생각되어 정렬로 풀기로 했다. 단순 내림차순으로 구현하면 가장 큰수가 나오지 않아서 Comparator중 람다를 이용해서 풀었다. 깊은 복사는 필요없을 수 있지만 혹시 몰라했다. compareTo에서 앞 뒤 문자 비교해서 정렬하는 것이 아닌 (앞 + 뒤) 와 (뒤 + 앞)을 비교했다.

 

내 코드

import java.util.Arrays;

class Solution {
 public String solution(int[] numbers) {
        String answer = "";
        String[] arr = new String[numbers.length];

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

        Arrays.sort(arr, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));
        
        if(arr[0].equals("0"))
            return "0";
     
        for(int i = 0; i< arr.length; i++){
            answer += arr[i];
        }
        

        return answer;
    }
}

 

다른 사람 풀이

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public String solution(int[] numbers) {
        String answer = "";

        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < numbers.length; i++) {
            list.add(numbers[i]);
        }
        Collections.sort(list, (a, b) -> {
            String as = String.valueOf(a), bs = String.valueOf(b);
            return -Integer.compare(Integer.parseInt(as + bs), Integer.parseInt(bs + as));
        });
        StringBuilder sb = new StringBuilder();
        for(Integer i : list) {
            sb.append(i);
        }
        answer = sb.toString();
        if(answer.charAt(0) == '0') {
            return "0";
        }else {
            return answer;
        }
    }
}

나와 달리 배열을 사용하는 것이 아닌 ArrayList를 사용해서 Collecltions.sort로 람다식을 만들었다. StringBuilder도 사용했는데 StringBuilder를 사용하면 문자열을 복사하는데 처리속도가 빠르다고 한다. Array.sort는 배열을 정렬하는 것이고 Collections.sort는 ArraysList나 LinkedList 와 같은 collection의 list를 정렬할 때 사용한다.