Largest Number

Largest Number

Explore - LeetCode

- 문제 내용 : 주어진 Integer의 Array를 조합해서 가장 큰 수를 만들어라

- 접근 방법

처음으로 접근한 방법은 0부터 9까지의 Array를 만들고 해당 Array에 첫번째 숫자 값으로 다시 Array를 넣는 방식을 선택했다.

가령 [[],[],[],[],[],[],[],[],[],[]] 이렇게 9개의 Array 안에 첫번째 integer 값이 7이라면 [[],[],[],[],[],[],[],[71,70,7],[],[]] 이런식으로 넣어 놓고, 주어진 모든 integer의 length를 더해서 dfs 형식으로 순환하면서 최고 값을 만들어내는 방식이다.

코드로는 아래와 같다. 

var largestNumber = function(nums) {
    if(nums.length === 0) return '';
    let fullLen = 0;

    let ten = new Array(10).fill(0).map(_=>new Array());

    for(let i = 0; i < nums.length; i++){
        let num = parseInt(nums[i].toString().charAt(0));
        ten[num].push(nums[i]);
        fullLen += nums[i].toString().length;
    }

    return getBigInt(ten, fullLen);

    function getBigInt(tens, fullLen){
        if(fullLen <= 0) return '';

        let copyTens = JSON.parse(JSON.stringify(tens));

        let index = 0;
        for(let i  = 9; 0 <= i; i--){
            if (0 < tens[i].length) {
                index = i;
                break;
            }
        }

        let max = 0;
        let curArr = [...copyTens[index]];

        curArr.sort((a, b) => b.toString().length - a.toString().length);
        let maxLen = curArr[0].toString().length;
        let maxIdx = 0;

        for (let i = 0; i < curArr.length; i++) {
            let curVal = curArr[i].toString();

            copyTens[index] = [...curArr.slice(0,i),...curArr.slice(i+1)];

            let tmp = parseInt(curVal + getBigInt(copyTens,maxLen - curVal.length));
            max = Math.max(max, tmp);

            if (tmp.length == maxIdx && tmp === max) {
                maxIdx = i;
            }
        }

        copyTens[index] = [...curArr.slice(0,maxIdx),...curArr.slice(maxIdx+1)];

        return curArr[maxIdx] + getBigInt(copyTens,fullLen - curArr[maxIdx].toString().length);
    }
};

복잡하기만 하고 정답이 아니라서 자세한 설명은 하지 않지만, 정답이 아닌 이유를 달자면

Integer의 범위를 벗어나는 숫자를 sum 하게 될경우 궁극적으로 Overflow를 발생하기 때문에 정답이 아니다.

가령 [Integer.MAX_NUM,Integer.MAX_NUM] 이렇게 들어가면 숫자로 sum을 하려고 하다 문제가 발생 하는 것이다.

return 값이 왜 String으로 지정되었는지 알게 된 부분이다.

 

두번째 접근 방법은 sorting처리를 잘 하는 것이다.

아이디어가 굉장히 좋은데, 나 스스로는 역시 착안하지 못할거 같다.

[a,b,c,d,e,f,g] 라고 하는 숫자의 모임이 주어 졌을 때, a와 b 또는 b와 a의 위치를 정의해서 두 integer가 합쳐졌을 때 가장 큰 순서대로 sorting 처리를 하게 된다.

그림으로 예를 들자면 아래와 같다.

이런 방식으로 2개의 숫자를 합쳤을 때 가장 큰경우를 가장 앞으로 Descending 정렬을 시켜주면 된다.

코드는 다음과 같이 간략해 진다.

var largestNumber = function(nums) {
    if (nums.length === 0) {
        return '';
    } else if (nums.every(num => num === 0)) {
        return '0'
    }
    nums.sort((a,b)=>{
        let asd = parseInt(a.toString() + b.toString());
        let des = parseInt(b.toString() + a.toString());

        if(asd < des){
            return 1;
        } else {
            return -1;
        }
    });

    return nums.join('');
};

여기서 Edge Case가 있는데 [0,0] 이렇게 들어오는 경우 '00'이 아닌 '0'이 return 되어야 한다.

이부분 처리를 위해 하기와 같이 별도 처리를 해주었다.

   if (nums.length === 0) {
        return '';
    } else if (nums.every(num => num === 0)) {
        return '0'
    }

 

시간 복잡도는

• nums.every : n
• sort : nlogn
• join : n

O(n + nlogn + n) => O(nlogn)

으로 nlogn 이다. 글자의 크기가 급격히 높아질 경우 Integer.MAX_NUM 처리 안되는건 동일하지만 첫번째 접근은 모든 경우를 integer로 치환해서 overflow가 났다면 두번째 접근은 2개의 숫자가 합쳐졌을 때만 안넘어 가면 처리 되는데는 문제가 없다.