프로그래머스 코딩테스트 문제: 가장 큰 수

level2의 문제이다.

보기엔 간단한 숫자 정렬 문제 같지만, 숫자를 int형이 아닌 String으로 해결해야하는 생각보다 까다로운 문제이다.

또한 엄청난 함정이 하나있다...!

 

https://programmers.co.kr/learn/courses/30/lessons/42746

 

간단하게 생각해서 큰 수가 앞에오면 된다는 생각은 절대절대 하면 안된다.

이 문제에서 큰 수를 만들기 위해서는 숫자를 띄어서 생각해야한다. 

예를들어 10을 10자체로 보기보단 1,0 으로 보는 것이다. 

모든 정수를 이었을때 제일 큰 자리수의 숫자가 클수록 큰 수가 된다. 

 

import java.util.*;
import java.lang.*;
class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        String[] arr=new String[numbers.length];

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

숫자의 맨 앞자리 (ex, 342이면 3)을 비교하고 같으면 다음 자리수를 비교하는 것에 대한 생각이 많았다. 

만약  33,34를 비교할때 3을 먼저 비교하고 그 다음 자리수를 비교하면 되지만 문제는 둘의 자리수가 다를때이다.

예를 들어 맨 앞자리가 3이면 34일 수도 있고 30492일 수도 있다. 

이렇게 되면 직접적인 비교가 어렵다.

 

따라서 숫자 하나하나를 비교하기 보단 풀고자하는 문제를 축소화 시켜서 풀어야 했다.

두개의 숫자를 문제처럼 이어보고 이를 직접 비교해야 하는 것이다. 

예를들어 9와 18을 비교하자. 

문제에서 원하는 답처럼 두 숫자를 이어보면 918과 189가 나온다. 

이렇게 되면 918이 더 큰 것임을 알 수 있고 이를 이용하여 내림차순으로 정렬하는 것이다. 

위의 과정을 거치면 우리가 원하는 순서대로 정렬이 될 것이다. 

 

 

여기서 제일 큰 함정은 배열에 0이 들어갈 수 있다는 것이다. 

만약 배열에 0이 1개 이상들어가게 되면 중복이 일어난다.

중복이 일어나면 내림차순으로 정렬했기 때문에 맨마지막에 0이 계속 쌓이게 된다.

예를 들어, 우리가 원하는 숫자는 0일때 중복이 일어나면 0000이 된다. 

따라서 0의 중복이 일어나면 다 무시하고 하나의 0만 출력하도록 처리를 해야한다.