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

 

 

처음에는 시간 복잡도를 생각하지 않고 무지성으로 해를 구했지만.. 시간초과ㅠ

 

처음 코드는

function solution(X, Y) {
    let result = []
    const num1 = Array.from(X).sort((a,b) => b-a)
    const num2 = Array.from(Y).sort((a,b) => b-a)
    
    
    num1.forEach((value, i)=> {
        if(num2.indexOf(value) !== -1) {
            let commonIdx = num2.indexOf(value)
            result.push(num2[commonIdx])
            num2.splice(commonIdx,1)
        }
    })
    return result.join('') === '' ? '-1' : +result.join('') === 0 ? '0' : result.join('')
    
}

 

forEach() 루프: O(n) 안에 indexOf(): O(n) 선형 탐색이 있었기 때문에 시간 복잡도는 O(n²) ......

어짜피 return 부분도 마음에 들지 않아서 다시 작성하기로 했다

 

 

function solution(X, Y) {
    const frequency = new Map();
    const result = [];
    
    // X의 숫자 빈도수 계산
    for(const num of X) {
        frequency.set(num, (frequency.get(num) || 0) + 1);
    }
    
    // Y와 비교하며 공통 숫자 찾기
    for(const num of Y) {
        if(frequency.get(num) > 0) {
            result.push(num);
            frequency.set(num, frequency.get(num) - 1);
        }
    }
    
    if(result.length === 0) return "-1";
    result.sort((a,b) => b-a);
    return result[0] === "0" ? "0" : result.join("");
}

 

O(n log n)으로 개선....

 

샘플이 적을 때는 큰 차이가 없지만 테스트 8 처럼 75% 개선 되는 테스트도 보였다