[24일차] Frequency Counter 복습

문제

Frequency Counter - sameFrequency

Write a function called sameFrequency. Given two positive integers, find out if the two numbers have the same frequency of digits.
Your solution MUST have the following complexities:
Time: O(N)
Sample Input:

sameFrequency(182,281) // true
sameFrequency(34,14) // false
sameFrequency(3589578, 5879385) // true
sameFrequency(22,222) // false

해결책

접근법

이 문제는 두 가지의 데이터가 주어지는데, 두 데이터를 구성하는 숫자가 같으면 true를 반환하고 아니면 false를 반환하는 문제이다. 단순하게 중첩 for루프를 이용해서 하나하나 비교하는 방법도 있지만 O(n^2)의 시간복잡도이며, 큰 데이터가 들어오기 시작하면 비효율성이 커진다. 좀 더 효율적으로 O(n)의 시간복잡도로 구현할 수 있는 방법이 바로 Frequency Counter 패턴을 이용하는 것이다.

같은 for루프를 사용하지만, 중첩으로는 사용하지 않는다.

function sameFrequency

function sameFrequency(first, second){
     //null check
    if(first === null || first === undefined || second === null || second === undefined) return 'false'
    
    //숫자열 1를 배열로 생성하기
    let arr1 = [];
    
    while(first > 0){
        arr1.push(Math.floor(first % 10));
        first = Math.floor(first / 10);
    }
    
    //숫자열 2를 배열로 생성하기
    let arr2 = [];
    
    while(second > 0){
        arr2.push(Math.floor(second % 10));
        second = Math.floor(second / 10);
    }
    
    //유효성 체크
    if(arr1.length !== arr2.length) return false;
    
    arr1 = arr1.sort();
    arr2 = arr2.sort();
    
    console.log("check " + arr1 + " ||||| " + arr2);
    
    for(let i = 0; i<arr1.length; i++){
        if(arr1[i] !== arr2[i]){
            return false;
        }
    }
    
    return true;
}

출처

https://www.udemy.com/share/105zfq3@CEAbfrQrVJgZKnMd7r7B-5BQeJScFHaLFdNvJX36D9N3y6a2nUQxfGIZ6cqgYSbuOg==/