제곱수 가진 배열인가요?

문제 설명

숫자를 포함하는 두 개의 배열이 주어지면, 첫 번째 배열의 모든 값들의 제곱수를 두 번째 배열이 가진다면 참을, 아니라면 거짓을 리턴하는 함수 same을 작성하는 문제다. 값의 빈도는 동일해야 하지만 순서는 상관없다.

예를 들어보자.
첫 번째 배열에 1, 2, 3이 있고 두 번째 배열에 4, 1, 9가 있다면 참이 반환되어야 한다.

두 번째 예를 생각해보자.
첫 번째 배열에 1, 2, 3이 있고 두 번째 배열에 1, 9가 있다면 2의 제곱에 해당하는 4가 포함되어 있지 않으므로 거짓이 된다.

세 번째 예를 생각해보자.
첫 번째 배열에 1, 2, 1이 있고 두 번째 배열에 4, 4, 1이 있다면 이 또한 빈도가 동일하지 않기 때문에 거짓을 반환해야 한다.

same([1,2,3], [4,1,9]);  // true
same([1,2,3, [1,9]]);  // false
same([1,2,1], [4,4,1]);  // false

첫 소스코드

function same(arr1, arr2) {
    // 만약 두 배열의 길이가 같지 않다면 답이 될 수가 없으니 거짓을 반환한다.
    if(arr1.length != arr2.length) {
        return false;
    }
    for (let i = 0; i < arr.length; i++) {
        // arr2를 돌면서 arr1의 개별 값의 제곱수에 해당하는 인덱스가 무엇인지 파악한다.
        let correctIndex = arr2.indexOf(arr1[i] ** 2);
        //  만약 대응하는 제곱수가 없다면 false를 반환한다.
        if (correctIndex === -1) {
            return false;
        }
        // 제곱수를 찾았다면 그 값은 arr2에서 제거해준다. 이를 통해 동일한 빈도수인지 체크한다.
        arr2.splice(correctIndex, 1);
    }
    return true;
}

시간복잡도(On^2)
for 루프 안에 indexOf를 사용하여 시간복잡도는 On^2이 나오는 코드다.

두번째 소스코드

function same(arr1, arr2) {
    if(arr1.length != arr2.length) {
        return false;
    }
    // 두 객체를 사용해서 각 배열의 개별 값의 빈도를 카운트 한다.
    let frequencyCounter1 = {};
    let frequencyCounter2 = {};
    // for~of 구문을 사용하여 두 객체가 배열의 각 요소에 대응하도록 해준다.
    for (let val of arr1) {
        frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1;
    }
    for (let val of arr2) {
        frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1;
    }
    console.log(frequencyCounter1);  // { 1: 1, 2: 2, 3: 1 }
    console.log(frequencyCounter1);  // { 1: 1, 4: 2, 9: 1 }
  
    for(let key in frequencyCounter1) {
        // frequencyCounter1의 각 key ** 2가 frequencyCounter2 의 key인지 확인해준다. 아니라면 false를 반환한다.
        if(!(key ** 2 in frequencyCounter2)) {
            return false;
        }
        // 값들의 대응(빈도수)을 확인해준다. 예를 들어 2가 두 개 있다면 4도 두 개 있어야 한다. 대응이 되지 않을 시 false를 반환한다.
        if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]) {
            return false;
        }
    }
    return true;
}


same([1,2,3,2],[9,1,4,4]);  // true
same([1,2,3,2,5],[9,1,4,4,11]);  // false

시간복잡도(On)
Frequency Counter 패턴을 적용한 소스코드다.
첫 번째 배열에 루프를 적용하여 두 번째 배열의 하위 루프에서 각 값을 확인하는 대신 각 배열에 한 번씩 개별적으로 루프를 적용한다.
두 개의 루프가 두 개의 중첩된 개별 루프보다 훨씬 낫다는 점을 염두에 두자.

Frequency Counter 패턴은 보통 객체를 주로 사용한다.
객체를 사용하여 프로파일을 구성하는 것은 배열이나 문자열의 내용을 분석하는 방법으로, 보통 배열이나 문자열과 같은 선형 구조를 구성하는 것이다.
그러면 해당 분석을 문자열이나 배열에서 생성된 다른 객체의 형태와 신속하게 비교할 수 있다.

좀 더 풀어서 말하자면, 두 개의 배열을 객체로 세분화하여 각 배열의 요소들을 분류한 다음, 각 배열을 비교하는 방법이다.