[Algorithm] 프로그래머스_가장 큰 수_정렬(Comparator 사용)

코딩테스트 연습 - 가장 큰 수

가장 큰 수

 

[문제 설명]

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

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

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

 

[제한 사항]

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

 

[입출력 예]

numbers	return
[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

 

풀이 과정

처음에는 순열을 구하여 가장 큰 값을 리턴하는 방식으로 구현하였는데 테스트 케이스 전부 실패(런타임 에러).

원인은 연산이 아니라 단순히 붙히는 값이라 길이가 100,000 이하라는 조건에 의하여 비교는 커녕 값을 담을 수가 없었다..... 방법은 입력받은 값을 배열또는 리스트로 처리해야 한다.

 

아래는 배열과 정렬, Comparator를 사용하여 해결 하였다.

1. 정렬 시 요소값을 비교하기 위해 입력받은 int배열을 string배열로 변환한다.

(* 예를들어 int배열에 3, 30이 요소로 존재할 경우 이 두 요소의 비교값은 '330'과 '303'이 된다. 비교 값을 만들 때 int로 합칠 경우 연산이 되어버리기 때문에 string으로 변환하여야 한다.)

 

2. Comparator를 사용하여 해당 string배열을 정렬 한다. (내림차순으로 정렬하도록 리턴해준다)

 

3. 예외사항) 제한사항의 배열의 요소가 '0'으로 들어올 수 있다고 한다.

* 테스트 케이스 11번에서 '0'으로 이루어진 배열이 입력값으로 들어온다. (이때 구할 수 있는 최대값은 '0'이 된다.)

이때, 내림차순으로 정렬된 배열의 0번째 인덱스값이 '0'이면 최대값이 '0'이니 그냥 '0'으로 출력하면 된다.

 

풀이

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

class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        int len = numbers.length;
        String[] strArr = new String[len];
        for(int i=0; i<len; i++){
            strArr[i] = String.valueOf(numbers[i]);
        }

        Arrays.sort(strArr, new Comparator<String>(){
            @Override
            public int compare(String o1, String o2){
                return (o2+o1).compareTo(o1+o2);
            }
        });
        
        if(strArr[0].equals("0")) answer = "0";
        else{
            StringBuilder sb = new StringBuilder();
            for(String x : strArr) {
                sb.append(x);
            }
            answer = sb.toString(); 
        }
        
        return answer;
    }
}

---