자바스크립트 배열에서 n번째 배수 관계의 두 숫자 찾기 (Set 활용)

정수로 이루어진 배열을 첫 번째 인수로, 숫자 n을 두 번째 인수로 받는 자바스크립트 함수를 작성해야 한다고 가정해 봅시다.

이 함수의 역할은 배열 안에 서로 n배 관계에 있는 두 숫자가 존재하는지 확인하는 것입니다. 즉, 한 숫자가 다른 숫자의 정확히 n배인 경우를 찾아야 합니다.

그러한 숫자 쌍이 배열에 하나라도 존재한다면 함수는 true를 반환하고, 존재하지 않는다면 false를 반환해야 합니다.

문제 이해하기

예를 들어 배열과 숫자가 다음과 같이 주어졌다고 해보겠습니다.

const arr = [4, 2, 7, 8, 3, 9, 5];
const n = 4;

이때 기대되는 출력은 다음과 같습니다.

const output = true;

그 이유는 배열에 2와 8이라는 숫자가 모두 포함되어 있고, 두 숫자 사이에 다음 관계가 성립하기 때문입니다.

8 = 2 * 4

풀이 접근 방식

가장 단순한 방법은 모든 숫자 쌍을 일일이 비교하는 것이지만, 이 경우 시간 복잡도가 O(n²)이 되어 배열이 클 때는 비효율적입니다.

더 효율적인 방법은 Set(집합) 자료구조를 활용하는 것입니다. 배열을 순회하면서 각 요소에 대해 다음 두 가지를 확인합니다.

현재 요소를 n으로 나눈 값(el / n)이 이미 등장했는지
현재 요소에 n을 곱한 값(el * n)이 이미 등장했는지

둘 중 하나라도 Set에 존재한다면, 그 값과 현재 요소가 n배 관계에 있다는 의미이므로 즉시 true를 반환하면 됩니다. 조건에 해당하지 않는다면 현재 요소를 Set에 추가한 뒤 다음 요소로 넘어갑니다. 이 방식은 시간 복잡도 O(n), 공간 복잡도 O(n)으로 문제를 해결할 수 있습니다.

예제 코드

위 접근 방식을 구현한 전체 코드는 다음과 같습니다.

const arr = [4, 2, 7, 8, 3, 9, 5];
const n = 4;

const containsNthMultiple = (arr = [], n = 1) => {
    const hash = new Set();
    for(let i = 0; i < arr.length; i++){
        const el = arr[i];
        const [left, right] = [el / n, el * n];
        if(hash.has(left) || hash.has(right)){
            return true;
        };
        hash.add(el);
    };
    return false;
};

console.log(containsNthMultiple(arr, n));

코드 설명

containsNthMultiple 함수는 빈 Set을 먼저 생성한 뒤, 배열의 각 요소를 순서대로 검사합니다. 매 반복마다 현재 요소 el을 기준으로 el / n과 el * n 값을 계산하고, 이 중 하나라도 Set에 이미 존재하는지 확인합니다.

존재한다면 n배 관계에 있는 쌍을 찾은 것이므로 곧바로 true를 반환하고, 그렇지 않으면 현재 요소를 Set에 추가합니다. 끝까지 탐색했는데도 해당하는 쌍을 찾지 못했다면 최종적으로 false를 반환합니다.

출력 결과

위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.

true

배열에 있는 2와 8이 8 = 2 × 4라는 n배 관계를 만족하기 때문입니다.