[프로그래머스] 최대공약수와 최소공배수 Kotlin

안녕하세요. 이번에는 프로그래머스 최대공약수와 최소공배수 문제를 풀어보려고 합니다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/12940

프로그래머스

---

Problem

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

 

[제한 사항]

○ 두 수는 1 이상 1000000 이하의 자연수입니다.

사진1. 입출력 예

---

Solution

class Solution {
    fun solution(n: Int, m: Int): IntArray {
        var gcdNum = gcd(n, m) 
        var answer = intArrayOf(gcdNum, n * m / gcdNum)

        return answer
    }

    fun gcd(a: Int, b: Int): Int {
        if(b == 0) {
            return a
        } 

        return gcd(b, a % b)
    }
}

 이번 문제는 유클리드 호제법을 알면 문제를 쉽게 풀 수 있습니다. 향후 유클리드 호제법에 대하여도 자세히 알아봐야겠습니다.

 

핵심 코드 (유클리드 호제법)

    fun gcd(a: Int, b: Int): Int {
        if(b == 0) {
            return a
        } 

        return gcd(b, a % b)
    }

 

1. 다른 사람 코드

class Solution {
    fun solution(n: Int, m: Int): IntArray {
        val gcd = gcd(n, m)

        return intArrayOf(gcd, n * m / gcd)
    }

    tailrec fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
}

  다른 사람의 코드를 공부하던 중 꼬리 trailrec에 대하여 알 수 있었습니다. 저의 코드와 많이 다르지는 않지만 Kotlin에서 제공하는 tailrec 꼬리재귀로 이루어진 코드를 가져와봤습니다.

 

trailrec 꼬리재귀함수를 사용하면 함수 호출이 반복문처럼 동작하도록 만들어 재귀 호출이 스택을 계속 쌓지 않고 반복되는 프로세스를 구현하여, 이로 인해 스택 오버플로우를 방지하고 성능을 향상할 수 있습니다.

 

이외에도, 장점이 있어서 향후 tailrec 꼬리재귀에 대하여 공부하고 포스팅해봐야겠습니다.

Performance

1. 내가 작성한 코드	2. 다른 사람 코드