[프로그래머스 Lv.0 / Swift] 유한소수 판별하기 With 최대공약수 & 최소공배수

이 문제는 최대공약수를 구하면 쉽게 풀리는 문제다.

최대공약수와 최소공배수는 알고리즘 문제에서 자주 나오는 소재 중 하나여서 한 번 제대로 알아보자!

 

먼저 유클리드 호제법(유클리드 알고리즘)에 따르면 2개의 자연수 a, b(a > b)에 대해서 a를 b로 나눈 나머지를 r이라 하면 a와 b의 최대공약수는 b와 r의 최대공약수와 같아진다.

그리고 다시 b를 r로 나눈 나머지 r'가 생성되고, r을 r'로 나눈 나머지 r''가 나오고... 쭉 반복해서 최종적으로 나머지 0이 나왔을 때의 나누는 수가 a와 b의 최대공약수가 된다. 글로만 보면 뭔 말인지 어렵다.

https://www.youtube.com/watch?v=Obs-HC5j5bI 

이 영상보면 이해가 팍 된다.

 

gcd(A, B)

-> A % B 결과 r이 0이 아니라면

-> gcd(B, r)

-> B % r 결과 r'가 0이 아니라면

-> gcd(r, r')

-> r % r' 결과 r''가 0이라면 최대공약수는 r'

 

이 방식으로 최대공약수를 구하는 gcd(Greatest Common Divisor) 함수를 만들어보면

func gcd(_ num1:Int, _ num2:Int) -> Int {
    let r = num1 % num2 // 나머지
    
    if r == 0 {
        return num2
    } else {
        return gcd(num2, r)
    }
}

 

나머지가 0이 아니면 다시 gcd()를 호출해서 나누는 작업을 반복(재귀함수)하도록 하고,

나머지가 0이 되었을 때의 나눴던 수가 최대공약수가 된다.

 

func gcd1(_ num1:Int, _ num2:Int) -> Int {
    
    let r = num1 % num2 
    
    if r != 0 {
        return gcd1(num2, r)
    }
    
    return num2
}

func gcd2(_ num1:Int, _ num2:Int) -> Int {
    if num1 % num2 != 0 {
        return gcd(num2, num1 % num2)
    }
    return num2
}

func gcd3(_ num1:Int, _ num2:Int) -> Int {
    return num1 % num2 == 0 ? num2 : gcd3(num2, num1 % num2)
}

원리를 알았으니 코드를 더 간결하고 다양하게 짜는 것도 쉽게 되지요👍

 

유한소수 판별하기 문제에는 최소공배수를 다루지는 않지만 최대공약수 공부한 김에 같이 해봅니다.

최소공배수는 최대공약수를 구했으면 쉽게 만들 수 있다.

 

최소공배수는 두 수 A, B가 있다면 A * B / gcd(A, B)로 계산하면 된다.

최소공배수 lcm(Least Common Multiple) 함수를 만들어보면

func gcd(_ num1:Int, _ num2:Int) -> Int {
    
    let r = num1 % num2 // 나머지
    
    if r != 0 {
        return gcd(num2, r)
    }
    
    return num2
}

// 최소공배수
func lcm(_ num1:Int, _ num2:Int) -> Int {
    return num1 * num2 / gcd(num1, num2)
}

최소공배수도 쉽게 뚝딱 완성

---

유한소수 판별하기

문제 설명

소수점 아래 숫자가 계속되지 않고 유한개인 소수를 유한소수라고 합니다. 분수를 소수로 고칠 때 유한소수로 나타낼 수 있는 분수인지 판별하려고 합니다. 유한소수가 되기 위한 분수의 조건은 다음과 같습니다.

• 기약분수로 나타내었을 때, 분모의 소인수가 2와 5만 존재해야 합니다.

두 정수 a와 b가 매개변수로 주어질 때, a/b가 유한소수이면 1을, 무한소수라면 2를 return하도록 solution 함수를 완성해주세요.

제한 사항

• a, b는 정수
• 0 < a ≤ 1,000
• 0 < b ≤ 1,000

입출력 예

a	b	result
7	20	1
11	22	1
12	21	2

입출력 예 설명

입출력 예 #1

• 분수 7/20은 기약분수 입니다. 분모 20의 소인수가 2, 5 이기 때문에 유한소수입니다. 따라서 1을 return합니다.

입출력 예 #2

• 분수 11/22는 기약분수로 나타내면 1/2 입니다. 분모 2는 소인수가 2 뿐이기 때문에 유한소수 입니다. 따라서 1을 return합니다.

입출력 예 #3

• 분수 12/21는 기약분수로 나타내면 4/7 입니다. 분모 7은 소인수가 7 이므로 무한소수입니다. 따라서 2를 return합니다.

Hint

• 분자와 분모의 최대공약수로 약분하면 기약분수를 만들 수 있습니다.
• 정수도 유한소수로 분류합니다.

Solution

import Foundation

func solution_유한소수_판별하기(_ a:Int, _ b:Int) -> Int {
    
    let child = a / gcd(a, b)
    let parent = b / gcd(a, b)
    
    if parent == 1 || child == parent { return 1 } // 정수는 유한소수

    for num in 2 ... parent {
        // num이 약수인 경우
        if parent % num == 0 {
            // 2, 5, 짝수가 아닐 때
            if num % 2 != 0 && num != 5 {
                // 소수 판별
                if isPrime(num) {
                    return 2
                }
            }
        }
    }
    return 1
}

// 최대공약수
func gcd(_ num1: Int, _ num2: Int) -> Int {
    if num1 % num2 != 0 {
        return gcd(num2, num1 % num2)
    }
    return num2
}

// 소수 판별
func isPrime(_ num: Int) -> Bool {
    for i in 2 ..< num {
        if num % i == 0 {
            return false
        }
    }
    return true
}

분자 child와 분모 parent를 최대공약수로 각각 나누어 기약 분수로 만들고,

정수는 유한소수니까 분모가 1일 때, 분모와 분자가 같을 때는 return 1 해주었다.

 

분모의 약수 중 2, 5, 짝수가 아니면서 소수인 수를 판단해서 소수면 return 2, 그렇지 않으면 return 1을 해서 문제를 해결했다.

 

소수는 1과 나 자신만을 약수로 갖는 수니까 2부터 차례대로 나누었을 때 나누어 떨어지는 수가 하나라도 없으면 소수로 판단한다.