[JAVA] 정렬 "가장 큰 수"

 

너무 복잡하게 생각하여 문제풀이를 실패했다.

 

단순하게 Sort에서 Compare 메소드를 오버라이드할때,

String o1, o2를 비교하면, o1+o2 와 o2+o1을 Integer로 변환해서

비교하여 정렬하는 방식으로 해야한다.

 

가장 이해하기 쉬운 코드리뷰이다.

import java.util.Arrays;
import java.util.Comparator;

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

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

        Arrays.sort(nums, new Comparator<String>() {
            public int compare(String o1, String o2) {
                return (o2 + o1).compareTo(o1 + o2);
            }
        });

        String ans = "";
        for (int i=0; i<numbers.length; i++)
            ans += nums[i];

        return ans.charAt(0) == '0' ? "0" : ans;
    }
}

 

위처럼 Compare메소드를 오버라이드해서 단순히 문자열을 더한걸 parseInt하여 비교하는 것이다.

 

다만  이 경우, 수행시간이 매우 커지는 현상이 발생하였다.

그에 따른 이유는 반복해서 String을 더하는 경우, new String을 하여 힙이 계속 쌓이게 된다고 한다.

 

이렇게 String을 계속해서 더하는 경우는 StringBuilder를 이용하라고 한다.

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;
        }
    }
}

위의 코드를 살펴보면, Collections.sort를 이용하여 비교한다(return 마이너스인것은 내림차순으로 정렬하기위한것)

 

StringBuilder sb = new StringBuilder(); 으로 선언해준다.

 

sb.append(값); 을해서 String에 값을 더해준다.

 

answer = sb.toString(); 을 통해서 StringBuilder->String으로 변환해준다.

 

이러한 경우 String값을 많이 사용하는 케이스어서 첫번째 코드보다 두번째 코드에서 9배가량의 속도차이가 났다.

StringBuilder를 이용하면 이렇게 메모리의 힙을 절약할 수 있다.