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

첫 번째 분수의 분자, 분모를 뜻하는 denum1, num1, 두 번째 분수의 분자, 분모를 뜻하는 denum2, num2가 매개변수로 주어진다. 두 분수를 더한 값을 기약분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 리턴하도록 solution 함수를 완성하라

 

 

입출력 예)

1 / 2 + 3 / 4 = 5 / 4 -> [5, 4] 리턴

9 / 2 + 1 / 3 = 29 / 6 -> [29, 6] 리턴

 

---

 

처음 접근한 방법은 두 분모 중 큰 숫자를 작은 숫자로 나눠서 나머지가 0이면 나눈 값(4 / 2 = 2)을 작은 분모, 분자에 곱해서 분수 덧셈을 진행하고, 0이 아니면 (1번째 분자 x 2번째 분모) + (1번째 분모 x 2번째 분자) / (1번째 분모 x 2번째 분모)를 통해 계산하려고 했다.

 

그러나 코드가 난잡해져서 어떻게 풀면 좋을지 고민하다가 마땅한 방법이 떠오르지 않아서 구글링했고 이런 풀이법을 봤다.

 

https://velog.io/@anna_developer/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%EB%B6%84%EC%88%98%EC%9D%98-%EB%8D%A7%EC%85%88

프로그래머스_분수의 덧셈

fun solution(denum1: Int, num1: Int, denum2: Int, num2: Int): IntArray {
    val denum3 = (num1 * denum2) + (num2 * denum1)
    val num3 = num1 * num2
    var min = 1 // 최소 공배수

    for (i in min..denum3) {
        if (denum3 % i == 0 && num3 % i == 0) {
            min = i
        }
    }
    val answer: IntArray = intArrayOf(denum3 / min, num3 / min)
    return answer
}

 

0이 아닐 경우 어떻게 처리할지까지는 내 생각과 똑같지만 반복문을 통해 최소공배수를 구하는 로직은 생각하지 못했다.

어떻게 돌아가는지 IDE에서 확인하다가 다른 사람들은 어떻게 풀었는지 궁금해서 프로그래머스에 저대로 제출하고 확인했는데, 유클리드 호제법이라는 걸 써서 푼 사람들이 많았다.

찾아보니 두 수의 최대공약수를 구하는 알고리즘이라는데, 이 알고리즘을 써서 푼 것보다 위의 코드가 더 알기 쉬워서 먼저 위의 코드의 작동원리를 좀 더 확인하고 유클리드 호제법을 확인해 봐야겠다.