[프로그래머스] 가장 큰 수 (정렬)-JAVA

[문제 설명]

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

 

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

 

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

[제한 사항]

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

[풀이]

해당 문제에서 최종 결과의 반환 타입은 String(문자열)입니다. 또한 문제를 쉽게 해결하기 위해서는 정렬을 사용해야 하는데, 많은 사람들이 알고 있다시피 int형 타입의 배열을 정렬하면 10이 6보다 크다는 결과가 출력됩니다.

 

그러나 우리가 구하고자 하는 답은 6이 10보다 커야되기 때문에 int형 타입으로 주어진 numbers 배열을 문자형으로 변환하는 것부터 시작합니다. 

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

arr라는 String 타입 배열에 모든 값을 문자열화 하여 저장합니다. 그 이후 정렬을 시작하는데, 여기서 주의할 점이 있습니다.

String[] arr = {"3", "30", "34", "5", "9"};
Arrays.sort(arr, Collections.reverseOrder());

//9 5 34 30 3

다음과 같은 arr 배열의 문자열 값들을 Arrays.sort를 이용하여 내림차순 하게 되면 9 5 34 30 3 순서로 정렬되게 됩니다. 그러나 우리가 원하는 것은 최댓값인 9 5 34 3 30 형태입니다. 이를 해결하기 위해 Comparator를 사용합니다. 

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

예를 들어 o1이 30이고 o2가 3이라 가정한다면, ("330").compareTo("303")의 결과를 리턴하게 됩니다. 당연히 둘의 차이를 계산하게 되면 양수 값이 리턴되게 됩니다. 값이 어떻게 나오던 양수값이 출력되면 둘의 자리는 교체되게 됩니다. 즉 9 5 34 30 3의 순서에서 9 5 34 3 30의 순서로 변환되는 것입니다. 

 

최종 코드입니다.

import java.util.Arrays;
import java.util.Comparator;
class Solution {
    public String solution(int[] numbers) {
     
		String[] arr = new String[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            arr[i] = numbers[i] + "";
        }

        Arrays.sort(arr, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                
                return (o2+o1).compareTo(o1+o2);
            }
        });
        
        String answer = "";
        
		if (arr[0].equals("0"))
			answer = "0";
		else {
			for (int i = 0; i < arr.length; i++) {
				answer += arr[i];
			}
		}
        
		return answer;
	}

}

참고로

        if (arr[0].equals("0"))
		answer = "0";

해당 코드의 의미는 주어진 배열이 [0,0,0,0] 같이 0으로만 이어질 경우 최종 리턴이 "0000"이 아닌"0" 이어야 하기 때문에 추가한 코드라고 보시면 됩니다.