[가장 큰 수]

 

 

맨 처음에는 정렬 알고리즘의 퀵 솔트를 사용해보려고 했지만 이론만 알고 사용해 본 적이 없어서 적용이 잘 안 되었다. 그래서 그냥 내가 알고 있는 정렬 해결책인 Arrays.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 합니다.

풀이 과정

(1) 우선 값을 더하는게 아니고 숫자를 붙여서 비교해야 하니까 String[]으로 변환해 준다.

String[] strNumArr = new String[numbers.length];
for (int i = 0; i < numbers.length; i++) {
	strNumArr[i] = Integer.toString(numbers[i]);
}

 

(2) 그다음에는 이제 sort를 사용한다. 나는 처음에 막혔던 게 어떻게 compare 메소드를 재정의하냐는 것이었다. 근데 진짜 원래 기본으로 정의되어 있는 compare 메서드를 떠올리니 생각하는 게 쉬워졌다. Integer 라이브러리 compare 메서드는 o1 == o2 는 0을 반환, o1

일반적으로 내림차순은 compare메소드에서 return o2-o1 이기 때문이다. 두 문자열을 합치고 정수형으로 변환해서 비교한다. (o2 + o1)과 (o1 + o2)를 비교하여 더 큰 값으로 정렬이 되는 식이다. 

Arrays.sort(strNumArr, new Comparator<String>() {
    @Override
    public int compare(String o1, String o2) {
        return Integer.parseInt(o2 + o1) - Integer.parseInt(o1 + o2);
    }
});

 

(3) 마지막으로 정렬된 문자열 배열을 하나의 문자열로 합쳐서 리턴한다. 

Arrays.stream(strNumArr).collect(Collectors.joining());

 

여기까지 하고 돌리면 테스트 11에서 실패가 뜬다...

 

이제 화가 난다. 그럼 잠깐 단 걸 먹는다. 나는 사탕을 먹었다.
테스트는 진짜 별의별 값이 다 오니까 0이 올 수도 있다. 0에 대해서 생각해 보자.
0을 여러개 넣고 돌렸는데도 값이 잘 나왔다. 그래서 0만 여러개 넣어봤더니 "00000"이 나왔다.

오케이 0은 "0"이니까 그렇구나 싶어서 코드를 추가하였다. 맨 앞자리가 0이면 "0"을 반환하도록!

그리하여 최종 결과는 이렇다.

class Solution {
    public String solution(int[] numbers) {

        String[] strNumArr = new String[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            strNumArr[i] = Integer.toString(numbers[i]);
        }
        
        // 위에서 진행한 식 람다로 변환
        Arrays.sort(strNumArr, ((o1, o2) -> Integer.parseInt(o2 + o1) - Integer.parseInt(o1 + o2)));

        return strNumArr[0].equals("0") ? "0" : Arrays.stream(strNumArr).collect(Collectors.joining());
    }
}

 

 

또, 문제를 풀면서 궁금했던 게 자바 sort는 내부에서 일반적으로 어떤 알고리즘을 사용하는지였다.

Java의 Arrays.sort() 의 알고리즘

우리의 친구 chatGPT에게 물어보니,

듀얼 피봇 퀵소트는 피봇이 두개인거겠지..? 다음에는 정렬의 종류에 대해서 적어봐야겠다.

+ 추가 (다른 사람 풀이)

답을 내고 다른 사람들의 풀이를 보는데 알아두면 좋을 것들이 많아서 적어본다.

1. 문자열을 합칠 때는 StringBuilder()를 쓰면 성능이 훨씬 좋아진다

StringBuilder sb = new StringBuilder();
        for(Integer i : list) {
            sb.append(i);
}

2. sort 다른 방법

// (1) 풀이 : 마지막에 순서 바꿨기 때문에 -Integer.compare() 해주기
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));
});


// (2) 풀이 : compareTo 메소드 사용하기
// 두개의 값을 비교하여 결과를 return 한다 (문자 비교, 숫자 비교 모두 가능)
Arrays.sort(nums, new Comparator<String>() {
    public int compare(String o1, String o2) {
        return (o2 + o1).compareTo(o1 + o2);
    }
});


// (3) 풀이 : stream에서 한번에 연산
// concat : 문자열 붙이기
 answer = Arrays.stream(numbers)
                .mapToObj(String::valueOf)
                .sorted((s1, s2) -> -s1.concat(s2).compareTo(s2.concat(s1)))
                .reduce("", (s1, s2) -> s1.equals("0") && s2.equals("0") ? "0" : s1.concat(s2));
                


// (4) 풀이 : 자리수를 비교하기
Arrays.sort(arr, new Comparator<String>() {
    @Override
    public int compare(String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();

        /* 다를 경우 */
        for (int i = 0; i < (len1 * len2); i++) {
            if (str1.charAt(i % len1) > str2.charAt(i % len2)) {
                return -1;
            } else if (str1.charAt(i % len1) < str2.charAt(i % len2)) {
                return 1;
            }
        }
        return 1;
    }
});

3. 0 해결 다른 방법

if(answer.charAt(0) == '0') {
	return "0";
}