프로그래머스 정렬2 가장 큰 수

문제 설명

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

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

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

제한 사항

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

입출력 예

문제 풀이(의식의 흐름)

문제를 풀기 위해 생각한 내용은 정렬을 언제 사용할 것이냐의 문제였다.
정렬을 사용하는것에는 2가지 경우의 수가 있다.
1. 가장 앞자리 숫자를 기준으로 정렬(코드 앞쪽에 자리잡는다.)
2. 모든 수열 만든다음에 정렬 후 가장 큰 수를 찾는다.
=> 아무리 생각해도 1.이 효율적으로 낫다는 결론을 가졌다.

그다음 고민은 어떻게 앞자리 수를 기준으로 정렬할 것인가이다. int 형은 9 보다 30이 크다. 하지만 String 형은 그렇지 않다. c가 ab보다 큰 것에서 착안 int[]를 String[]로 바꿔줬다. 또한 String의 장점은 덧셈이 아닌 String끼리 합쳐진다는 것이다.

import java.util.*;
class Solution {
    public String solution(int[] numbers) {
        String[] ints = new String[numbers.length];
        for(int i =0; i<numbers.length;i++) ints[i] = String.valueOf(numbers[i]);
		Arrays.sort(ints, new Comparator<String>() {

			@Override
			public int compare(String o1, String o2) {

				return ((o2 + o1).compareTo(o1 + o2));
			}
		});
        if(ints[0].equals("0")) return "0";
        String answer = "";
        for(String a : ints) answer += a;
        return answer;
    }
}

문제점

처음 코드를 작성시 Override를 사용하지 않고

Arrays.sort(ints, Collection.reverseOrder()));

를 사용하니 원하던 결과가 나오지 않았다.

왜냐하면 "30" 과 "3"을 비교시 "30"을 더 큰 수로 인식하여 결과값으로 "330"이 아닌 "303"을 반환하였기 때문이다.

이 를 해결하기 위해선 Collection.reverseOrder()) 대신 Comparator 인스턴스를 생성하고 compare() 메서드를 오버라이드 하면 된다. 풀이에서는 문자열을 합쳐서 비교하기 때문에 위에 말했던 오류가 발생하지 않는다.