[알고리즘] 배열 안의 요소 비교

문제

A와 B 배열이 있는데 B배열안의 요소들이 A배열 요소들의 제곱값인지 판별하는 함수를 만들어야한다.

예를 들면

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

 

(1) 1번 풀이

function same(arr1, arr2) {
  if (arr1.length !== arr2.length) {
    return false;
  }
  for (let i = 0; i < arr1.length; i++) {
    let correctIndex = arr2.indexOf(arr1[i] ** 2);
    if (correctIndex === -1) {
      return false;
    }
    arr2.splice(correctIndex, 1);
  }
  return true;
}

문제는 풀리지만 for문안에 splice를 써서 시간복잡도가 O(n^2)이다.

 

 

(2) 2번 풀이

function same(arr1, arr2){
    if(arr1.length !== arr2.length){
        return false;
    }
    let frequencyCounter1 = {}
    let frequencyCounter2 = {}
    for(let val of arr1){
        frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1
    }
    for(let val of arr2){
        frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1        
    }
    for(let key in frequencyCounter1){
        if(!(key ** 2 in frequencyCounter2)){
            return false
        }
        if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]){
            return false
        }
    }
    return true
}

객체를 사용해서 시간복잡도를 O(n)으로 낮췄다.