자바스크립트에서 두 배열 간 제곱 관계 확인하기

문제 정의

두 개의 숫자 배열 arr1과 arr2를 각각 첫 번째와 두 번째 인수로 받는 자바스크립트 함수를 작성해야 합니다.

이 함수는 arr2의 모든 요소가 순서와 상관없이 arr1에 포함된 어떤 요소의 제곱일 경우에만 true를 반환해야 합니다.

예를 들어, 함수의 입력이 다음과 같다고 가정해 보겠습니다 −

입력

const arr1 = [4, 1, 8, 5, 9];
const arr2 = [81, 1, 25, 16, 64];

출력

const output = true;

위 예시에서 9² = 81, 1² = 1, 5² = 25, 4² = 16, 8² = 64이므로 arr2의 모든 요소가 arr1 요소의 제곱에 해당합니다. 따라서 결과는 true입니다.

접근 방법: 빈도 카운팅

이 문제를 효율적으로 해결하려면 단순히 값의 존재 여부만 확인해서는 안 됩니다. 중복된 값이 있을 수 있으므로 각 제곱 값의 빈도까지 함께 추적해야 합니다.

핵심 아이디어는 다음과 같습니다 −

먼저 두 배열의 길이가 같은지 확인합니다. 길이가 다르면 즉시 false를 반환합니다.
arr1의 각 요소를 제곱한 값을 키로 사용하는 빈도 맵(객체)을 만듭니다.
arr2의 각 요소를 순회하며 해당 값이 빈도 맵에 존재하는지 검사합니다.
존재하면 빈도를 하나 감소시키고, 존재하지 않거나 빈도가 이미 0이라면 false를 반환합니다.

코드 구현

다음은 위 접근 방식을 구현한 전체 코드입니다 −

const arr1 = [4, 1, 8, 5, 9];
const arr2 = [81, 1, 25, 16, 64];

const isSquared = (arr1 = [], arr2 = []) => {
  // 길이가 다르면 제곱 관계가 성립할 수 없음
  if (arr1.length !== arr2.length) {
    return false;
  }
  // arr1 요소들의 제곱값 빈도 맵 생성
  const freq = {};
  for (const num of arr1) {
    const square = num * num;
    freq[square] = (freq[square] || 0) + 1;
  }
  // arr2의 각 요소가 제곱 맵에 존재하는지 검사
  for (const num of arr2) {
    if (!freq[num]) {
      return false;
    }
    freq[num]--;
  }
  return true;
};

console.log(isSquared(arr1, arr2));

출력 결과

true

코드 설명 및 주의할 점

이 알고리즘의 시간 복잡도는 O(n)입니다. 객체를 활용한 해시 조회는 평균적으로 O(1)이 걸리기 때문에, 이중 반복문이나 indexOf를 반복 호출하는 O(n²) 방식보다 훨씬 효율적입니다.

또한 freq[num]-- 처리 덕분에 동일한 제곱 값이 여러 번 등장하는 경우에도 정확하게 대응할 수 있습니다. 예를 들어 arr1 = [2, 2], arr2 = [4, 4]인 경우에도 올바르게 true를 반환합니다.

구현 시 흔히 저지르는 실수도 주의해야 합니다. indexOf로 찾은 인덱스 변수 대신 배열 요소 자체를 -1과 비교하거나, 단순히 값의 존재만 확인하고 실제 제곱 연산 없이 비교하는 경우가 대표적입니다. 반드시 제곱 연산을 수행한 뒤 비교하고, 빈도까지 고려해야 정확한 결과를 얻을 수 있습니다.