[프로그래머스] 숫자짝꿍

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/131128

이 문제는 1레벨 문제이지만 무려 1시간10분이 걸려 풀었다.

완전탐색 방식으로 10분만에 풀었지만, 시간초과가 나왔다..

조금씩 수정하며 시도했지만 똑같았고, 아예 방법을 바꿔 풀었다.

이 방법이 어떤 알고리즘인지는 알지는 못하겠으나, 설명을 해보자면,

하나씩 완전 탐색하지 않고 0~9까지 몇 개의 숫자가 중복되는지 체크 후, 두 배열을 비교하여 더 적은 수만큼 정답 배열에 더해줬다.

이렇게 하면 최소 On2의 시간복잡도에서 최악 On2(반복문안에서 중복된 숫자만큼만 반복하기때문)의 시간복잡도로 바뀌기 때문에 시간초과가 나지 않는다.

코드는 아래와 같다.

const solution = (X,Y)=> {
    const arr = Array(10).fill(0);
    const arr2 = Array(10).fill(0);
    [...X].forEach(i=>arr[i]++);
    [...Y].forEach(i=>arr2[i]++);
    let answer = []
    arr.forEach((num,idx)=>{
        const result = Math.min(num,arr2[idx])
        Array(result).fill(undefined).forEach(i=>answer.push(idx))
    })
    answer = answer.sort((a,b)=>b-a).join('')
    return answer[0] == 0 ? '0' : answer || '-1'
}