Lv2. [정렬] - 가장 큰 수 - (sort와 compare, compareTo)

---

[ 문제 링크 ]

프로그래머스 Lv2. 가장 큰 수

 

[ 문제 설명 이미지 ]

정렬

여러개의 정수가 주어지는데, 이 정수들의 숫자를 이어붙혀 만들 수 있는 수중 가장 큰 숫자를 구한다.
6, 10 2 세개의 숫자가 주어졌다고 가정, 이때 가능한 조합은 6가지가 나온다.
그중 가장 큰 수는 6210이 된다.

 

핵심은 배열의 모든 요소를 사용하는 경우의 수를 모두 구하고 그중 가장 큰 값을 구하는것이며,

이때 함정은 한자릿수 두자리수 한자릿수 합치면 4자리밖에 되지 않지만 
만약 배열이 3자리수 10개로 구성된다면 총 30자리의 숫자가 만들어 진다.
이는 integer의 범위가 넘어간다. double을 사용한다고 하더라도 배열이 조금만 길어진다고 하더라도 범위를 넘어가므로 Long을 사용해야 한다.

하지만 String으로 반환하므로 해당 부분에 대한 문제는 발생하지 않을것으로 보인다.

가장 큰 수를 만들기 위해서는 큰 수부터 다뤄야 한다.
하지만 숫자로서 큰 숫자가 아닌 글자 순서로서 큰 수로 구성되는 특징이 있으므로 문자열 사전적 정렬을 해야한다.
숫자를 문자로 바꾸고 문자를 내림차순으로 정렬한 후에 조합하면 가장 큰 수를 만들 수 있게 된다.

---

[풀이 1] 버블정렬 

a.compareTo(b)

compareTo 메소드는 대상값과 매개변수의 값을 비교한다.

정수 비교의 경우는 단순하게 크다(1) 같다(0) 작다(-1) 와 같은 결과값을 리턴한다.

 

문자열 비교의 경우는 사전 순으로 비교하는 데 사용되고, 정수만큼 단순하지는 않다.

 

기준 값에 비교 대상 값이 포함되어 있을 경우 서로의 문자열 길이의 차이 값을 리턴하고,

만약 포함되어 있지 않다면 각 문자열의 아스키 코드를 비교한다.

 

ABCDEF와 A를 비교하면 A는 ABCDEF에 포함되어 있기 때문에 길이의 차 6 - 1인 5를 반환한다.

ABCDEF와 G를 비교하면 G는 ABCDEF에 포함되어 있지 않기 때문에 길이가 아닌 A(97) - G(103)인 -6을 반환한다.

 

만약 두 문자열의 길이가 모두 1이상일 경우 ABCDEF와 BG에 대한 비교는 A(97) - B(98) 이므로 -1을 반환하지만

예를들어 ABCDEF와 AG를 비교할때 두 값이 일치하는 A는 각각 기준 값 비교대상 값 모두 건너뛴다.

따라서 B(98) - G(103)  = -5 와 같은 연산 결과가 나온다.

ABCDEF와 ABG를 비교하면 C(99) - G(103) 인 -4가 되고

ABCDEF와 AF를 비교하면 B(98)-F(102)인 -4가 된다.

import java.util.stream.IntStream;
import java.util.stream.Collectors;
class Solution {
    public String solution(int[] numbers) {
        String[] strNums = new String[numbers.length];
        int index = 0;
        while (index < numbers.length) strNums[index] = String.valueOf(numbers[index++]);

        for(int i = 0; i < strNums.length; i++) {
            for(int j = i+1; j < strNums.length; j++) {
                String s1 = strNums[i];
                String s2 = strNums[j];
                if ((s1 + s2).compareTo(s2 + s1) < 0) {
                    strNums[i] = s2;
                    strNums[j] = s1;
                }
            }
        }
        index = 0;
        StringBuffer sb = new StringBuffer();
        while (index < strNums.length) sb.append(strNums[index++]);
        if(sb.toString().charAt(0) == '0') return "0";
        return sb.toString();
    }
}

 

정렬에서 compareTo를 활용하여 사전적 정렬을 수행한다.

만약 두 값의 합의 차이가 0보다 작을 경우 이후 값을 이전 값과 자리를 바꿔 정렬한다.

if(sb.toString().charAt(0) == '0') return "0";

마지막 return 직전에 위와같은 작업을 처리하는 이유는

모든 데이터가 0만 들어오는 경우를 처리한것이다.

이 처리를 하지 않는다면 테스트 11 에서 실패한다.

 

 

[결과] 좌측 그림과 같이 시간초과로 인한 실패를 하게 된다.

 

이는 버블정렬이 O(n²)이라는 10만개 * 10만개 = 100억개의 연산이므로 우리는 연산의 속도를 줄여야 한다.

 

기본적으로 자바 유틸 혹은 컬렉션에서 정렬 함수를 제공한다. (아마도 퀵정렬일것임)

(Arrays 혹은 List)

 

 

 

 

 

 

---

[풀이 2] 자바 내장 메소드를 활용한 퀵정렬

Arrays.sort() / Compartor.compare / String.compareTo()

 

Comparator.compare()

Comparator의 compare은 순서에 대한 두 인수를 비교하여 나오는 return 값에 의해 두 값의 위치에 대한 정렬이 결정된다.

• arg1  <  arg2 = return < 0 (오름차순)
• arg1  >  arg2 = return > 0 (내림차순)
• arg1 == arg2 = return = 0 (순서 유지)

compare은 기본 정렬이 오름차순이다.

반환된 값이 0이라면 순서 변경없이 유지되고, 음수라면 오름차순 / 양수라면 내림차순 정렬이 된다.

만약 순수 값 그 자체로 양/음수값(-1) 혹은 0을 직접 반환한다면 요소 하나하나에 대한 비교가 아닌 배열 전체에대한 오름차순 혹은 내림차순, 변경없음이 진행된다. 

 

compareTo

따라서 우리는 여기서 compare의 반환값을 두 값을 기준으로 비교하여 구해야 한다.

이때 단순히 두 값에 대해서 비교하여 내림차순 정렬할 경우 문제가 발생한다.

만약 주어진 값이 3과 30이 나왔을때 그대로 내림차순을 할경우 303이 되어버린다.

두 수의 조합 중 큰 값은 303보다 330이 더 크기 때문에 우리는 이에대한 처리를 해줘야 한다.

그래서 compareTo() 메소드를 사용하여의 기준값/비교값을 (다음값+현재값)/(현재값+다음값)으로 적용해야 한다.

330/303을 비교하면 3은 포함하므로 건너뛰고 그 이후 3과 0을 비교하기 때문에 양수가 나온다.

양수라면 오름차순 이므로 30과 3중에 3이 먼저 세팅되어 정렬된다.

 

위의 compareTo 코드를 적용하여 compare 메소드를 구현해보자.

import java.util.stream.IntStream;
import java.util.stream.Collectors;
class Solution {
    public String solution(int[] numbers) {
        String[] strNums = new String[numbers.length];
        int index = 0;
        while (index < numbers.length) strNums[index] = String.valueOf(numbers[index++]);

        Arrays.sort(strNums, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o2 + o1).compareTo(o1 + o2);
            }
        });
        index = 0;
        StringBuffer sb = new StringBuffer();
        while (index < strNums.length) sb.append(strNums[index++]);
        if(sb.toString().charAt(0) == '0') return "0";
        return sb.toString();

    }
}

 

 

---

[나의 풀이] 스트림을 적용해 보았다.

import java.util.stream.IntStream;
import java.util.stream.Collectors;
class Solution {
        public String solution(int[] numbers) {
                    return IntStream.of(numbers).mapToObj(String::valueOf)
                        .sorted((o1, o2) ->  -(o1+o2).compareTo(o2+o1))
                        .reduce((s1, s2) -> (s1+s2).equals("00") ? "0" : s1+s2).get();

    }
}