프로그래머스) 분수의 덧셈 (Swift)

📌 문제

코딩테스트 연습 - 분수의 덧셈 | 프로그래머스

 

 

📌 접근 방식

두 분수를 더하여 기약분수로 만드는 알고리즘은 크게 세 단계로 나누어진다.

 

1. 통분: 서로 다른 분모를 같게 만든다.
2. 덧셈: 분모를 같게 하기 위하여 곱해진 분자를 서로 더한다.
3. 약분: 분모, 분자를 더 이상 나눌 수 없을 때까지 나눈다. → 최대공약수 이용

여기서 통분과 덧셈은 단순한 사칙연산으로 해결이 가능하지만, 약분에서는 최대공약수를 구하여 한번에 나누는 게 핵심이다.

 

최대공약수을 구하는 방법은 유클리드 호제법을 이용했는데, 이에 대한 설명은 아래에 자세히 다루었으니 참고 하자.

[재귀] 유클리드 호제법과 최대공약수, 최소공배수

 

최대공약수를 구하는 건 크게 두 방식이 있는데, 여기서는 반복적으로 구하는 알고리즘을 선택했다.

1. 반복적으로(iteratively) 구하는 방법
2. 재귀적으로(recursively) 구하는 방법

 

(+) 원래 통분을 할 때 최소공배수를 이용하려고 했으나, 되려 더 번거로운 것 같아 실제 solution 함수에서 이용하지는 않았다.

 

📌 코드

import Foundation

func solution(_ numer1:Int, _ denom1:Int, _ numer2:Int, _ denom2:Int) -> [Int] {
    
    // 통분 이후 서로를 더하여 새 변수에 대입
    var numer = numer1 * denom2 + numer2 * denom1
    
    // 통분하기 위해 분모는 서로를 곱하여 새 변수에 대입
    var denom = denom1 * denom2
    
    // 약분을 위해 분모와 분자의 최대공약수를 구한다.
    var gcd = findGCD(numer, denom)
    
    // 최대공약수로 서로 약분
    numer = numer / gcd
    denom = denom / gcd
    
    // 기약분수 분모와 분자를 반환
    return [numer, denom]
}

// 최대공약수를 구하는 함수 작성
func findGCD(_ x: Int, _ y: Int) -> Int {
    var a = 0
    var b = max(x, y)
    var r = min(x, y)
    
    // r이 0이 될 때까지 반복문을 도는데, 그 순간의 b를 GCD로 판단한다.
    while r != 0 {
        a = b
        b = r
        r = a % b
    }
    
    return b
}

// 아래의 코드는 쓰지 않았다.
// 최소공배수를 구하는 함수 작성
func findLCM(_ x: Int, _ y: Int) -> Int {
    // 서로 곱하여 앞서 구한 최소공약수로 나눈다.
    return (x * y / findGCD(x, y))
}