Count Array Pairs Divisible by K

Count Array Pairs Divisible by K

목적

integer의 배열이 nums가 주어진다.

주어진 nums에서 2개의 pair를 선택해서 곱한 결과가 k로 나뉘어지는 경우가 몇 번인가?

단, pair가 (1,2)이면 (2,1)과 동일하다. 

 

접근 방법

Brute force 접근

가장 쉬운 접근은 모든 경우의 수를 곱샘 하는 것이다.

만약

nums = [1,2,3,4,5], k = 2

가 주어지면,

[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[2,5],[3,4],[3,5],[4,5]

를 만들 수 있고 이중에서 2로 나뉘어 지는 것은

2,3,4,5,6,8,10,12,15,20

중에서 2,4,6,8,10,12,20이 된다.

모든 경우의 수를 따지고 k로 % 연산을 진행할 경우 최대 $ O{lengthOfNums^2} $ 이 된다.

 

GCD를 이용한 접근

일단 GCD가 무었이고 어떻게 개발하는 지는 

2021.06.27 - [Problem Solving] - Greatest common divisor (gcd) 최대 공약수 구하기, Euclidean algorithm 유클리드 알고리즘

를 참고하자.

 

위의 문제를 다음과 같이 풀어서 설명할 수 있다.

• 2개의 pair의 곱이 k로 나뉘어 지는가?
• 그 만들어진 곱이 k의 구성원을 포함하고 있는가?

다음과 같이 예를 들어보자.

만약 (9 * 10)의 페어가 있다고 생각해 보자. 이 페어는 90을 만든다.

$ 90 = 3 * 3 * 2 * 5 $ 

90은 3 2개와 2 하나 그리고 5하나로 이루어 진다.

90은 3으로도 나누어질 수 있고 3두개로도 나누어질 수 있다. 3 두개 2한개로도 나누어질 수 있도 있고 3두개 2하나 5하나로도 나누어질 수 있다.

즉, 90을 구성하는 값들로만 나누어질 수 있다.

주어진 k가 저 구성원에 속한다면 90이라는 페어는 k로 나누어진다고 생각할 수 있다.

 

이런 속성을 이용해서 다음과 같이 k와 pair의 관계를 생각해 볼 수 있다.

만약에 k값이 70이고 pair중 하나가 60이라고 생각해 보자.

70으로 나누어지는 pair를 찾기위해서 60은 어떤 소인수를 갖는 상대방을 찾아야 하는가?

단, 하나 소인수로 7을 갖고있는 상대방이 있기만 하면 된다.

그 외에 어떤 소인수 값을 갖고 있는지는 관심의 범위가 아니다.

위의 방식을 이용해서 문제를 풀어나가 보자.

 

k를 구성하는 소인수는 무엇인가?

우선 k를 구성하는 모든 소인수의 곱을 구해야 한다.

위에서 7,5,2로 주어진 70이 있는데 이 것은 10*7 일수도 있고 14*5 일수도 있다.

즉, 2개의 곱으로 70을 만들어낼 수 있는 모든 경우의 수를 찾고 pair와 비교해서 나머지 부족한 곱을 찾으면 된다.

설명이 조금 이상한데 아래 내용을 보면 이해하기 쉬울 것 같다.

70으로 나누어지는 곱은 77과 30이 된다.

왜냐 하면 77의 구성 요소에 7이 있고, 30의 구성요소에 10(5*2)이 있기 때문이다.

 

구성요소를 이용해서 2개의 pair 곱 찾기

k인 70의 2개 pair는 어떻게 찾을까요?

1부터 70까지 모든 값을 %로 모듈레이션 해주면 된다.

function getDivisor(k){
    let arr = new Array();

    for(let i = 1; i <= k; i++){
        if(k % i === 0){
            arr.push(i);
        }
    }
    return arr;
}

70을 divisor하면

[1,  2,  5,  7, 10, 14, 35, 70]

를 얻을 수 있습니다. pair a가 7를 갖어 갔으면 pair b는 10을 찾으면 됩니다.

 

이제 pair a의 값이 77일때 77이 어떤 구성요소를 70과 공유하는지를 알아야 한다.

 

2개 값의 GCD 계산하기

주어진 2값의 공통 곱값을 찾는 방법은 GCD가 된다.

function gcd(a,b){ //a가 크고, b가 작은거
    if(b === 0) return a;
    if(a < b) {
        return gcd(b,a);
    } else {
        return gcd(b, a%b)
    }
}

상세한 내용은 위의 링크를 참고 바란다.

2개의 공통수를 찾고 k를 나누면 우리가 목표로 하는 pair b의 구성요소를 찾을 수 있다.

let val = Math.floor(k / gcd(k, num));

k가 70이고 gcd(70, 77)은 7임으로 우리가 찾아야할 구성요소는 10이다.

그럼 10을 구성요소로 갖는 nums의 갯수를 찾기만 하면 답이 된다. 그런데 10은 무슨 구성요소일까?

10도 결국은 [1,  2,  5,  7, 10, 14, 35, 70] 이 구성요소 주 하나가 된다.

즉, 어떤 주어진 num과 70의 구성 요소간에 share하는 값을 미리 저장해 놓는다면 계산하기 편하다.

for(const divisor of divisors){
    if(num % divisor === 0){
        counters[divisor]++;
    }
}

지금 주어진 값이 77이고 77은 7과 10으로 나누어질 수 있다.

counter[7]++;

counter[10]++;로 표현 할 수 있다.

만약에 10을 갖고있는 pair a가 들어온다면 7을 갖고 있는 num의 갯수를 더하면 답이되고,

7을 갖고 있는 pair a가 들어오면 10을 갖고 있는 num의 갯수를 더하면 답이된다.

result += counters[val];

코드

https://gist.github.com/theyoung/38e2b3307f706ee925fe1a63cade149f

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var coutPairs = function(nums, k) {
    let divisors = getDivisor(k);
    let counters = new Array(k+1).fill(0);
    let result = 0;

    for(const num of nums){
        let val = Math.floor(k / gcd(k, num));
        result += counters[val];

        for(const divisor of divisors){
            if(num % divisor === 0){
                counters[divisor]++;
            }
        }
        console.log(counters)
    }

    return result;

};


function gcd(a,b){ //a가 크고, b가 작은거
    if(b === 0) return a;
    if(a < b) {
        return gcd(b,a);
    } else {
        return gcd(b, a%b)
    }
}

function getDivisor(k){
    let arr = new Array();

    for(let i = 1; i <= k; i++){
        if(k % i === 0){
            arr.push(i);
        }
    }
    return arr;
}

시간 복잡도

시간복잡도는 기본적으로 nums를 순회함으로 $ O(N) $ , GCD의 Time complexity는 log(min(a,b))임으로 

$ O(N * log(min(a,b))) $ 가 된다. 여기에 divisor를 순회함으로 $ O(N * log(min(a,b)) * numberOfdivisors) $가 최종 시간 복잡도가 된다.