시간초과

let arr = [];

function makeNumber(currentArr, remainingArr){
    if(remainingArr.length === 0){
        arr.push(currentArr.join(""));
        return;
    }
    for(let i=0;i<remainingArr.length;i++){
        const nextArr = [...currentArr, remainingArr[i]]
        const nextRemaining = remainingArr.filter((_, index) => index !== i);
        
        makeNumber(nextArr, nextRemaining)
    }
};

function solution(numbers) {
    makeNumber([], numbers);
    console.log(arr);
    arr.sort((a,b)=> a-b);
    
    let answer = '';
    answer = arr.pop();
    
    return answer;
}

초기아이디어

단순히, 모든 주어진 배열의 값들의 조합을 배열에 저장

배열 정렬 후, 제일 큰 수 리턴이므로 pop하기

실패이유

작성하신 DFS 기반의 순열 알고리즘은 배열의 길이가 N일 때 N!의 경우의 수.

• 만약 숫자가 10개라면: $10! = 3,628,800$번 반복
• 숫자가 20개라면: $20! \approx 2.4 \times 10^{18}$번 반복...

프로그래머스 '가장 큰 수' 같은 문제는 입력 배열의 길이가 최대 100,000
100,000!은 우주가 끝날 때까지 계산해도 안 끝나는 수치

그래서 메모리가 터지거나(core dumped) 시간이 초과되는 것입니다.

해결: "정렬 규칙"을 바꾸기

모든 조합을 다 만들 필요가 없습니다. "두 수를 이어 붙였을 때 더 큰 쪽이 앞으로 오게" 정렬만 하면 끝남

핵심 로직: 숫자 a와 b가 있을 때, a+b와 b+a 중 무엇이 더 큰지 비교합니다.

예: 3과 30이 있을 때

• 3 + 30 = "330"
• 30 + 3 = "303"

330이 더 크므로 3이 30보다 앞에 와야 합니다.

---

최종코드

function solution(numbers) {
    let answer = '';
    
    answer = numbers
        .map(num => num.toString())
        .sort((a,b) => (b+a) - (a+b))
        .join("")
    
    return answer[0] === '0' ? '0' : answer;
}

어떻게 모든 숫자에 대해서 정렬이 가능?

JavaScript의 sort()는 내부적으로 Quick Sort나 Timsort 같은 고성능 알고리즘사용

예를 들어 숫자가 3개(A, B, C) 있을 때:

1. A와 B를 합쳐보고 A가 더 유리하다고 판단.
2. B와 C를 합쳐보고 B가 더 유리하다고 판단.
3. 그러면 수학적으로 A는 C보다 무조건 유리하게 됩니다 (A > B 이고 B > C 이면 A > C).

특이 테스트케이스

000의 경우 0으로 출력