링크

문제 링크

문제 설명

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의 최대 길이를 보고 바로 지웠다

그래서 생각한 두 번째 알고리즘

1. Arrays.sort() compare 메소드 오버라이드를 통해 맨 앞자리 숫자들을 기준으로 내림차순 정렬
2. 맨 앞자리 숫자가 같은 원소들 끼리는 그 다음 자리를 비교
3. 만약 그러고도 그 뒤가 같으면? 2번을 반복

그러나 이 방식은 문제에서 주어진 입출력 예제가 친절하게 나와있어서 그렇지 자릿수가 다른 원소들의 비교는 뒷자리 처리가 더 필요하다는 것을 깨닫게되었다

근데 처음엔 이 방식 밖에 없다고 생각하고 @Override compare 메소드안에 코드를 꾸역꾸역 넣다가 현타가 왔다

오랜시간 고민하니 구글링이 절실해졌다 ㅜ

그렇게 알아낸 최종 알고리즘

1. Arrays.sort()를 오버라이드 하는 것은 맞게 접근했다.
2. 그러나 두 원소를 String으로 치환해서 s1+s2와 s2+s1간의 크기를 비교해서 사전순으로 누가 뒤에 있는지를 따지자

정답코드 말고 알고리즘 영감만.. 얻기위해 구글링했는데 "사전순 비교" 한 마디에 정답이 나와버렸다!..

코드

import java.util.*;
class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        boolean except = true;
        String[] num = new String[numbers.length];
        
        for(int i = 0; i < num.length; i++){
            num[i] = String.valueOf(numbers[i]);        
            if(numbers[i] != 0) except = false;
        }
        
        Arrays.sort(num, new Comparator<String>(){
           @Override
            public int compare(String n1, String n2) {
                return (n2+n1).compareTo(n1+n2);
            }
        });
        for(int i = 0; i < num.length; i++)
            answer += num[i];
        if(except) answer = "0";
        return answer;
    }
}

except 변수는 numbers의 변수들이 0밖에 없을때 "00000~"을 반환하는 예외 케이스를 위해 선언하였다.

아직 갈 길이 한참 멀다...