[Hackerrank] Between Two Sets 문제 해설 - Algorithms

[Hackerrank] Between Two Sets 문제 해설 - Algorithms > Implementation / Easy

1월 04, 2018

Between Two Sets

1. 문제 설명

이 문제는 정수로 이루어진 두 배열 A, B의 원소 중 다음 조건을 충족하는 정수(x)의 갯수를 구하는 문제이다.

All elements in A are factors of x.
x is a factor of all elements in B.

이를 다르게 표현하면 다음과 같이 표현 할 수 있다.

x mod a[i] = 0 for every a[i] in A
b[i] mod x = 0 for every b[i] in B

예를 들어, A = {2, 6}이고 B = {12}일 경우 x에 속할 수 있는 값은 6과 12가 된다.

*원본 링크 : https://www.hackerrank.com/challenges/between-two-sets/problem

변수 설명

A: a[i]로 구성된 정수 배열
B: b[i]로 구성된 정수 배열
n: A의 원소 갯수
m: B의 원소 갯수
x: 위의 조건을 충족하는 정수

2. Input Format

첫번째 줄에는 n과 m값이 주어진다.

두번째 줄엔는 A의 원소인 a[i] 값이 주어진다.

세번째 줄엔는 B의 원소인 b[i] 값이 주어진다.

3. Output Format

A와 B 배열에서 위의 조건을 만족하는 정수 x의 갯수 출력

4. 제약조건

Sample Input

2 3
2 4
16 32 96

Sample Output

Solution

처음 접근했던 방법은 위에서 주어진 식을 그대로 풀어서 문제를 해결하는 식이었다.
순서는 다음과 같다.

B에 속해있는 원소들의 공약수를 모두 구한다.
1번에서 구한 공약수 중 A에 속한 모든 원소로 나누었을 때, 나머지 값이 모두 0이 되는 공약수가 있는지 찾는다.
2번을 충족하는 공약수로 이루어진 새로운 배열을 만든다.
3번에서 구한 배열의 length 값을 출력한다.

위의 방법으로 작성한 코드는 다음과 같다.

function getTotalX(a, b) {
    const commonDivisorForB = getCommonDivisor(b);
    const result = getReverseCommonDivisor(a, commonDivisorForB);

    return result.length;
}

function getCommonDivisor(arr) {
    const result = [];
    const minValue = Math.min.apply(null, arr);

    for (let i = 1; i <= minValue; i++) {
        const tmpArr = arr.filter((num) => {
            return num % i === 0;
        });

        if (tmpArr.length === arr.length) {
            result.push(i);
        }
    }

    return result;
}

function getReverseCommonDivisor(arr1, arr2) {
    const arr1Length = arr1.length;
    const arr2Length = arr2.length;
    const result = [];

    for (let i = 0; i < arr2Length; i++) {
        let cnt = 0;
        for (let j = 0; j < arr1Length; j ++) {
            if (arr2[i] % arr1[j] === 0) {
                cnt++;
            }
        }

        if (arr1Length === cnt) {
            result.push(arr2[i]);
        }
    }

    return result;
}

function main() {
    var n_temp = readLine().split(' ');
    var n = parseInt(n_temp[0]);
    var m = parseInt(n_temp[1]);
    a = readLine().split(' ');
    a = a.map(Number);
    b = readLine().split(' ');
    b = b.map(Number);
    var total = getTotalX(a, b);
    process.stdout.write("" + total + "\n");

}

해당 방법으로 통과는 했으나, 알고리즘 문제인데 너무 단순하게 풀었기 때문에 다른 방법이 있을 것이라고 생각했다.

그래서 떠올린 방법이 최소공배수와 최소공약수를 이용한 방법이었다.
일단 다시 한 번 위의 조건을 살펴보자.

x mod a[i] = 0 for every a[i] in A
b[i] mod x = 0 for every b[i] in B

1번 조건은 A의 공배수를 나타낸다.
2번 조건은 B의 공약수를 나타낸다.
1번과 2번 조건을 모두 만족하기 위해서는 A의 공배수이면서 B의 공약수인 정수를 구하면 된다.

공배수는 최소공배수 x n으로 표현 할 수 있고,
공약수는 최대공약수의 약수로 표현 할 수 있다.
때문에 문제 풀이 방법은 다음과 같아 진다.

A에 속한 원소들의 최소공배수를 구한다.
B에 속한 원소들의 최대공약수를 구한다.
A의 최소공배수와 B의 최대공약수 사이에 나머지가 0인 정수의 갯수를 구한다.

최대 공약수는 유클리드 호제법을 통해 구할 수 있다.

function getGCD(num1, num2){
        return num2 === 0 ? num1 : getGCD(num2, num1 % num2);
    }

최소 공약수는 다음과 같이 구할 수 있다.

function getLCM(num1, num2){
        return num1 * num2 / getGCD(num1, num2);
    }

이 블로그 검색

armadillo.ko