[프로그래머스 *Java] - 가장 큰 수 (순열로 접근x -> 런타임 에러 발생)

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

프로그래머스

 

조건
제한시간 : 30분

그냥 간단하게 생각을 했었다. 
문제를 보고서 순열로 값을 만들어서 max 값 비교를 통해서 결과 값을 출력하려 했다..
하지만? 일단 런타임 에러 발생으로 접근을 잘못했다고 판단하였다.

순열의 시간 복잡도는 n! 
따라서 아래에 문제에서 언급한 길이 값을 순열로 만들 시? 최악의 상황은 100000! 이 나오게 된다.
numbers의 길이는 1 이상 100,000 이하입니다.
numbers의 원소는 0 이상 1,000 이하입니다.

순열로 푸는 방식이 아니라? 정렬을 통해서 문제를 풀어야 한다.
아래 실패 코드와 
성공 코드를 보고 확인하자.

순열로 접근했을 시 나오는 에러ㅜ

10000! 는 굉장히 큰 수 인가보다..

 

실패 코드(순열 접근)

class Solution {
    static boolean[] visited;
    static int[] arr;
    static int max = Integer.MIN_VALUE;
    
    public void perm(int depth, int len, int[] numbers) {
        
        // base case
        if(depth == len) {
            StringBuilder sb = new StringBuilder();
            for (int i : arr) {
                sb.append(numbers[i]);
            }
            int nInt = Integer.parseInt(sb.toString());
            max = Math.max(max, nInt);
            return;
        }
        
        // recur
        for (int i = 0; i < numbers.length; i++) {
            if(!visited[i]) {
                visited[i] = true;
                arr[depth] = i;
                perm(depth + 1, len, numbers);
                visited[i] = false;
            }
        }
    }
    public String solution(int[] numbers) {
        int len = numbers.length;
        arr = new int[len];
        visited = new boolean[len];
        perm(0, len, numbers);
        
        return String.valueOf(max);
    }
}

 

성공 코드(정렬 접근)

import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        String[] num = new String[numbers.length];
		for(int i = 0; i < numbers.length; i++) {
			num[i] = String.valueOf(numbers[i]);
		}

		Arrays.sort(num, new Comparator<String>() {
			@Override
			public int compare(String o1, String o2) {
				return (o2 + o1).compareTo(o1 + o2);
			}
		});

		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < num.length; i++) {
			sb.append(num[i]);
		}
        String answer = sb.toString();
        if(answer.charAt(0) == '0') { 
			return "0";
		}

		return answer;
    }
}