[Implementation] Between Two Sets

문제 설명:

  There will be two arrays of integers. Determine all integers that satisfy the following two conditions:

1. The elements of the first array are all factors of the integer being considered
2. The integer being considered is a factor of all elements of the second array

These numbers are referred to as being between the two arrays. Determine how many such numbers exist.

 

Example

a = [2, 6]
b = [24, 36]

There are two numbers between the arrays: 6 and 12.
6%2 = 0, 6%6 = 0, 24%6 = 0 and 36%6 = 0 for the first value.
12%2 = 0, 12%6 = 0 and 24%12 = 0, 36%12 = 0 for the second value. Return 2.

 

Function Description

Complete the getTotalX function in the editor below. It should return the number of integers that are betwen the sets.

getTotalX has the following parameter(s):

• int a[n]: an array of integers
• int b[m]: an array of integers

Returns

• int: the number of integers that are between the sets

Input Format

The first line contains two space-separated integers, n and m, the number of elements in arrays a and b.
The second line contains n distinct space-separated integers a[i] where 0 <= i < n.
The third line contains m distinct space-separated integers b[j] where 0 <= j < m.

 

 

 

 

내 풀이:

 

// 최대공약수 구하기
func gcd(a: Int, b: Int) -> Int {
    guard b != 0 else { return a }
    return gcd(a: b, b: a%b)
}

// 최소공배수 구하기 (두 수의 곱 == 최대공약수 * 최소공배수, 최소공배수는 두 수의 곱 나누기 최대공약수)
func lcm(a: Int, b: Int) -> Int {
    return (a / gcd(a: a, b: b)) * b
}

func getTotalX(a: [Int], b: [Int]) -> Int {
    var lcmA = a[0]
    var gcdB = b[0]
    
    // get a's lcm
    if a.count >= 2 {
        for num in a {
            lcmA = lcm(a: lcmA, b: num)
        }
    }
    // get b's gcd
    if b.count >= 2 {
        for num in b {
            gcdB = gcd(a: gcdB, b: num)
        }
    }
    // 1. a의 최소공배수와 b의 최대공약수 같다면, 정답은 1개
    // 2. b의 최대공약수가 a의 최소공배수보다 크다면, 나머지의 갯수를 변수에 넣기 (loop문 돌릴거임)
    // 3. b의 최대공약수가 a의 최소공배수보다 작다면, 정답은 0개 (본인보다 큰 숫자에 안나누어짐)
    var result = lcmA == gcdB ? 1 : lcmA < gcdB ? gcdB / lcmA : 0
	
    // 결과가 0이 아니라면 loop문 실행하여, 최대공약수로 나누어떨어지지 않는 수마다 result에서 1빼기
    if result != 0 {
        for num in 1...result {
            if gcdB % (lcmA * num) != 0 {
                result -= 1
            }
        }
    }

    return result
}

 

 

 

 

회고:

  b의 최대공약수가 a의 최소공배수보다 작을 것이란 예상을 전혀 하지 못하고 풀었다. 모든 경우의 수를 생각할 수 있도록 더 노력해야겠다.

또한, 최소공배수와 최대공약수를 구하는 식을 전보단 능숙하게 쓰지만, 더 능숙하게 작성할 필요가 있다.

// 최대공약수
func gcd(a: Int, b: Int) -> Int {
	guard b != 0 else { return a }
    return gcd(a: b, b: a%b)   
}

// 최소공배수 (두 수의 곱 == 최소공배수 * 최대공약수)
func lcm(a: Int, b: Int) -> Int {
	return (a * b) / gcd(a: a, b: b)
}

 

주저리 )  그래도 맨 처음 알고리즘 문제 풀었을때를 돌아보면 많이 발전한게 느껴진다. 모르겠으니 해보자는 마인드와 아 모르는데..라며 포기하는 마인드는 천지차이 같다. 무엇이든 할 수 있다 생각하고 접근하는 것이 역시 중요하다. 모르는 것은 문제 없지만 모른다고 놔버리는 것은 문제이다. 꾸준하게 계속 고민하고 풀자!