[알고리즘 || 프로그래머스] 숫자 짝꿍

 

 

대략적인 풀이는 30분 정도 만에 했는데, 계속 시간 초과가 떴다.

11-15는 BigInt 가 분명해!

 

<통과 못한 코드 1>

function solution(X, Y) {
    const Xcount = new Array(10).fill(0);
    const Ycount = new Array(10).fill(0);

    X.split("").map(v => Xcount[+v]++);
    Y.split("").map(v => Ycount[+v]++);

    const resultCount = [];
    for (let i = 0; i < 10; i++) {
        resultCount[i] = Xcount[i] < Ycount[i] ? Array.from({ length: Xcount[i] }, () => i) : Array.from({ length: Ycount[i] }, () => i);
    }

    const result = resultCount.flat()
    if (!result.length) {
        return "-1"
    } else {
        return String(BigInt(result.sort((a, b) => b - a).join("")));
    }
}

Array.from 을 이용해 자리수가 공통된 개수만큼 들어있는 array 를 해당 index 에 넣어주는 방식으로 요리조리 해봤는데,

시간 오류가 나는 것은 동일했다.

[[0], [1, 1], [0]......[0]] <- 이런 방식으로 만든 후, 

result 로 1차원 배열로 만들어준 뒤 [0, 1, 1, 0, 0, ...0]

수들을 오름차순으로 정렬, Join 으로 합친 후 Bigint 로 만들고 (윗자리의 0을 제거하기 위함 & 범위가 bigint 해당)

그 다음에 다시 String 으로 만들어서 return 하는 방식이다.

 

다른것보다 시간 복잡도를 많이 잡아먹는 곳을 찾아야했다.

 

 

<통과 못한 코드 2>

function solution(X, Y) {
    const Xcount = new Array(10).fill(0);
    const Ycount = new Array(10).fill(0);

    X.split("").map(v => Xcount[+v]++);
    Y.split("").map(v => Ycount[+v]++);

    const resultCount = [];
    for (let i = 0; i < 10; i++) {
        if (!Xcount[i] == 0 && !Ycount[i] == 0) {
            const minCount = Math.min(Xcount[i], Ycount[i]);
            let string = '';
            for (let j = 0; j < minCount; j++) {
                string += `${i}`
            }
            resultCount[i] = string;
        }
    }
    const result = resultCount.reverse().map(BigInt).join("");
    return result.length > 0 ? result : "-1";
}

배열로 하면 어쨌든 시간 복잡도가 크게 나올거란 생각이 들었고, 

이 부분을 보고 힌트를 얻었다.

분명 string 으로 출력하는게 더 가볍겠지!

이전 코드에서 [5, 5] 같은 배열을 넣어주는 대신, 문자열로 만들어주기로 했다.

for 문을 이용해 string에 '5', '5' 를 붙여서 그 값을 넣어줬는데, 이것도 시간초과가 떴다.

당연하다. 시간을 줄여야 하는데 for 문을 중첩시켰으니 O(n²) 가 나올게 분명함!!

그렇다면 어떻게 합쳐야 반복문을 두번 쓰지 않을까? 

 

 

<통과한 코드>

function solution(X, Y) {
    const Xcount = new Array(10).fill(0);
    const Ycount = new Array(10).fill(0);

    X.split("").map(v => Xcount[+v]++);
    Y.split("").map(v => Ycount[+v]++);

    let str = '';
    for (let i = 9; i >= 0; i--) {
        const minCount = Math.min(Xcount[i], Ycount[i]);
        str += Array.from({ length: minCount }, () => i).join("");
    }

    if (!str.length) {
        return "-1"
    } else if (Number(str) == 0) {
        return '0';
    } else {
        return str
    }
}

array로 만들지 말고 바로 string 으로 만들자!

그리고 for 문의 순서를 바꿨다.

배열은 sort 를 할 수 있지만, string은 그런 고차함수가 없기 때문에 (그리고 한 덩어리라 안됨)

큰 수 먼저 string 에 붙여줬다.

이전에는 0, 1, 1, 4, 4 순서로 배열에 들어갔다면, 

지금은 4, 4, 1, 1, 0, 0 순으로 붙는다. 

 

완성된 str의 length 가 0 이라면 => 일치하는 짝궁 숫자가 하나도 없는 것. "-1"을 리턴

str을 숫자로 바꿨을 때 0이 나온다면? => "000000" "00" 이런 형태이기 때문에 0이다. "0" 을 리턴

두가지 경우가 아니라면 "124" "2450" 등 처럼 유효한 자리값을 가지는 숫자임. str 을 바로 return 해준다.

 

시간은 좀 걸렸지만 스스로 풀어내서 나 자신 칭찬해!

 

 

 

<다른 사람의 코드> char 를 이용

function solution(X, Y) {
    let result = '';
    const numObj = {};

    for (const char of X) {
        numObj[char] = (numObj[char] || 0) + 1;
    }

    for (const char of Y) {
        if (!numObj[char]) continue;
        result += char;
        numObj[char]--;
    }

    if (result === '') return '-1';
    if (+result === 0) return '0';
    return [...result]
        .map((num) => +num)
        .sort((a, b) => b - a)
        .join('');    
}