[프로그래머스] 분수의 덧셈 - Kotlin(코틀린)

문제

첫번째 분수의 분자와 분모를 뜻하는 numer1, denom1, 두번째 분수의 분자와 분모를 뜻하는 numer2, denom2 가 매개변수로 주어집니다. 두 분수를 더한 값을 기약 분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해보세요.

제한사항

• 0 < numer1, denom1, numer2, denom2 < 1,000

입출력 예

numer1	denom1	numer2	denom2	result
1	2	3	4	[5, 4]
9	2	1	3	[29, 6]

 

---

코드(Kotlin) - 내 코드

class Solution {
    fun solution(numer1: Int, denom1: Int, numer2: Int, denom2: Int): IntArray {
        val sumNumer = (numer1 * denom2) + (numer2 * denom1)
        val sumDenom = denom1 * denom2
        val maxValue = if(sumNumer > sumDenom) sumNumer else sumDenom
        
        var resultNumer = sumNumer
        var resultDenom = sumDenom
        for(i in 2 .. maxValue) {
            if(sumNumer % i == 0 && sumDenom % i == 0) {
                resultNumer = sumNumer / i
                resultDenom = sumDenom / i
            }
        }
        return intArrayOf(resultNumer, resultDenom)
    }
}

코드(Kotlin) - 다른 사람 코드

class Solution {
    fun solution(numer1: Int, denom1: Int, numer2: Int, denom2: Int) {
        return intArrayOf(numer1 * denom2 + numer2 * denom1, denom1 * denom2).apply {
            gcd(this[0], this[1])
               .let { gcdValue ->
                   this[0] /= gcdValue
                   this[1] /= gcdValue
               }
       }
   }
   
   fun gcd(a: Int, b: Int): Int = if(b == 0) a else gcd(b, a % b)
}

풀이 과정

1. 두 분수를 합산하기 위해 두 분모를 곱하여 두 수의 공통분모를 만든다.

2. 2부터 max 값(합산된 분모와 분자 중 큰 수)까지 반복문을 돌며 두 수 모두 나누어떨어지는 값을 찾는다.

 

문제 자체가 어렵다고 느껴지진 않았으나, 다른 사람들의 코드를 보니 문제 출제 의도를 파악하지 못했다는 생각이 들었다. 문제 출제 의도에 해당하는 내용을 다루기 위해 해당 게시물을 작성하게 되었다.

---

알게된 내용

해당 문제는 두 수 사이에 존재하는 최대공약수(GCD)를 구하는 유클리트 알고리즘을 사용하기에 최적화된 문제이다.

 

먼저 유클리드 알고리즘의 원리는

- A > B 라고 가정했을 때, A를 B로 나눈 나머지가 N이고, N이 0 일 때 B가 최대공약수(GCD)라고 할 수 있다.

- 만약 N이 0이 아니라면, N이 0이 될때까지 B와 N(=A%B)으로 위 과정을 반복한다.

 

유클리트 알고리즘을 사용하는 방법으로는 아래 두가지 방법이 있다.

//반복문을 사용하는 방법
fun gcd(A: Int, B: Int): Int {
    var N: Int = 0
    while (B != 0) {
        N = A % B
        A = B
        B = N
    }
    return A
}

//재귀를 사용하는 방법
fun gcd(A: Int, B: Int): Int {
    if (B == 0) {
        A
    } else {
        gcd (B, A % B)
    }
}