가장 큰 수

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

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

 

문제 설명

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"

 

문제 회고

사실 어떻게 해야될지 가닥을 못잡고 다른사람 풀이를 보고 이해해서 구현한 문제이다. 개인적으로 뭔가 이런 스타일의 문제들이 요즘 트렌드인 것같다.
핵심은 붙여보는 것이다. 뭔소리인지는 밑에 설명을 통해 보자.

6과 10이 들어왔을 때,
"6" + "10" = "610" and "10" + "6" = "106" 
여기서 610과 106을 비교하면 610이 더 크므로 순서를 바꾸지 않는다.
다음 10과 2를 보자
"10" + "2" = "102" and "2" + "10" = "210"
이번에는 뒤의 210이 더 크다.
이런경우 순서를 바꿔줘야 한다.
[6, 2, 10] 이 된다.
6과 2를 비교해보자
"62" and "26" 앞이 크므로 바꾸지 않는다.

최종 정렬 상태는 [6, 2, 10] 이고 이를 문자열로 붙이면 답이다.
주의할 점은 [0, 0, 0, 0] 인 경우 답은 "0000"이 아닌 "0"이 되어야 한다는 것이다.

 

코드 

import java.util.*;
 
 
class Solution {
    public String solution(int[] numbers) {
        
        StringBuilder answer = new StringBuilder();
        LinkedList<Integer> numList = new LinkedList<>(); 
        
        for ( int num : numbers ) numList.add( num );
        
        Collections.sort( numList, new Comparator<Integer>() {
            public int compare ( Integer a, Integer b ) {
                
                String strA = a + "" + b;
                String strB = b + "" + a;
                
                int numA = Integer.parseInt( strA );
                int numB = Integer.parseInt( strB );
                
                return numB - numA;
            }
        });
        
        if( numList.get(0) == 0 ) return "0";
        
        for ( int num : numList ) answer.append(num); 
        return answer.toString(); 
    }
}