[프로그래밍 문제] 가장 큰 수

문제 설명

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

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

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

제한 사항

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

입출력 예 (입력/출력)

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

생각한 방법

1. 재귀를 사용해 모든 경우의 수 탐색
2. 가장 큰 수만 저장

import java.util.*;
import java.util.stream.*;

class Solution {
    String highNumber = "";
    
    public String solution(int[] numbers) {
        recursive("", Arrays.stream(numbers)
            .mapToObj(String::valueOf)
            .collect(Collectors.toList()));
        if(highNumber.startsWith("0")) return "0";
        return highNumber;
    }
    
    public void recursive(String number, List<String> numbers){
        int len = numbers.size();
        if(len==1){
            if(highNumber.compareTo(number+numbers.get(0))<0){
                highNumber = number+numbers.get(0);
            }
        }
        for(int i=0;i<len;i++){
            List<String> copy = new ArrayList<>(numbers);
            recursive(number+copy.remove(i), copy);
        }
    }
    
}

결과

재귀 함수를 사용해 가장 큰 수를 찾아보았지만, 최대 !100000의 함수 호출이 생겨 메모리 초과 문제로 실패했다.

다른사람 풀이 참고

import java.util.*;
class Solution {
    public String solution(int[] numbers) {
        return Arrays.stream(numbers)
            .mapToObj(String::valueOf)
            .sorted((x, y)->(y+x).compareTo(x+y))
            .reduce((x, y)->x+y)
            .map(x->x.startsWith("0")?"0":x)
            .get();
    }
}

출처: https://yeonyeon.tistory.com/156 [연로그]

풀이 해석

1. 이어붙였을 때 큰수를 내림차순 정렬
2. 정렬된 값들은 이어붙여 출력

int[]를 스트림으로 변환 후 mapToObj와 valueOf 함수를 통해 String으로 형변환한다.

정렬 부분이 중요한데, 이어붙여서 큰 수를 정렬해야하므로 y+x에서 compareTo를 호출해서 비교

Collections의 joining 함수를 통해 정렬한 값들은 이어붙인다.

최종값을 리턴하되 앞이 0으로 시작하면 0을 리턴