[🐨 커뮤러닝/7기/Java] ] 가장 큰 수 (Bubble Sort)

🌟 가장 큰 수

📃 문제

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예로, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

🚫 제한 사항

numbers의 길이는 1 이상 100,000 이하입니다.
numbers의 원소는 0 이상 1,000 이하입니다.
정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.
만약 문자열이 0으로만 이루어져 있을 경우 "0" 을 return 합니다.

👀 입출력 예

 

🤔 풀이 방법

단순 숫자의 정렬은 현재 상황에 맞지 않다. 또 모든 경우의 수를 확인해보는 것도 무모하다. 따라서 문자열을 버블 정렬을 통해서 크기순으로 정렬해야 한다.

💻 풀이 코드

1️⃣ Bubble Sort 사용

public class 가장_큰_수 {
    public static void main(String[] args) {
        String answer = "";

        // 풀이 순서 : 숫자 배열 -> 문자 배열 -> 정렬 -> 문자열
        int[] numbers = {6, 10, 2};

        // (1) 숫자 배열 -> 문자 배열
        String[] strNumbers = new String[numbers.length];

        for (int i=0; i<numbers.length; i++) {
            strNumbers[i] = "" + numbers[i];
        }

        // (2) 정렬
        for (int i=1; i<strNumbers.length; i++) {
            for (int j=0; j<strNumbers.length-i; j++) {
                String s1 = strNumbers[j];
                String s2 = strNumbers[j+1];
                if ((s1+s2).compareTo(s2+s1) < 0) {
                    strNumbers[j+1] = s1;
                    strNumbers[j] = s2;
                }
            }
        }

        // (3) 문자열
        for (String str : strNumbers) {
            answer += str;
        }
        
        // cf) 예외처리
        if (answer.startWith("0")) return "0";

        System.out.println(answer);
    }
}

2️⃣ Arrays.sort() 사용 ①

// (2) 정렬 부분만 수정 with Comparator 사용
Arrays.sort(strNumbers, new Comparator<String>() {
    public int compare(String o1, String o2) {
        // return (o1+o2).compareTo(o2+o1); // 오름차순
        return (o2+o1).compareTo(o1+o2); // 내림차순
    }
});

3️⃣ Arrays.sort() 사용 ② : 람다식 활용

// (2) 정렬 부분만 수정
// 방법 2 에서 + 람다식 활용
Arrays.sort(strNumbers, ((o1, o2) -> (o2+o1).compareTo(o1+o2)));

➡️ Arrays.sort 의 두번째 인자는 Comparator 하나로 고정되어있기 때문에 new Comparator 생략가능하며, Comparator 에는 compare 메소드 하나만 존재하기 때문에 또한 생략이 가능하다. 추가로 첫번째인 StrNumbers 의 타입이 String 이므로 compare 메소드의  매개변수가 String 인것은 고정적이므로 어떤 문자열을 사용할지는 명시해주어야 한다. 마지막으로 -> 를 통해 구현 내용을 작성하면 된다.

4️⃣ Stream 사용 (자바 8 이상)

public class 가장_큰_수 {
    public static void main(String[] args) {
        int[] numbers = {6, 10, 2};
        
        String answer = IntStream.of(numbers)
            .mapToObj(n->String.valueOf(n))
            .sorted((s1,s2)->(s2+s1).compareTo(s1+s2))
            .collect(Collectors.joining());
        
        if (answer.startsWith("0")) answer = "0";

        System.out.println(answer);
    }
}