[프로그래머스,Java] Level2:가장 큰 수

문제분석

목표: 주어진 수를 조합하여 가장 큰 수를 반환하면된다.

 

보통, 문제설명처럼 순열 알고리즘을 통해, 모든조합을 찾은뒤에 가장큰수를 찾는법도 존재는한다.

 

하지만, 제한사항을 보면 numbers의 길이가 최대 10만이다.

 

10만개의 숫자를 모든조합을 돌리면 연산수가 아득하게 높다.. 무조건 시간초과다

 

그러면 순열을 안쓰고 효율적으로 확인하는방법을 찾아야한다.

 

문제를 들어오기전에 힌트로 '정렬' 키워드를 주워졋다.

 

보아하니, 정렬을 이용해서 푸는문제인거같으니, 정렬로 통해 접근해보자.

 

정렬은,  두개의 원소를 비교하면서 자리를결정한다.

 

그렇다면, 6 10 이주어지면 어떻게 가장큰수로 변환할까..

 

문자열로 6+10 과 10+6 으로 비교하면된다!

 

610과 106을 비교한다. 610이더크니, 6, 10으로 정렬하는거다.

 

->이렇게 하나씩 정렬하면 가장큰 순서를 만드는 배열이 완성된다.

 

 

문제풀이

 

import java.util.*;
class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        String[] str = new String[numbers.length];
        for(int i=0;i<numbers.length;i++){
            str[i]=numbers[i]+"";
        }
        
        Arrays.sort(str,(a,b)->(b+a).compareTo(a+b));
        StringBuilder sb= new StringBuilder();
        for(String data:str){
            sb.append(data);
        }
        
        answer=sb.toString();
        
        if(answer.startsWith("0")){
            return "0";
        }
        
        return answer;
    }
}