TIL231226 D26 팀프로젝트 시작 - SNS

앱개발 기초 팀프로젝트 주간이다. SNS 앱 만들기가 주제로 나왔다. 팀원들과 회의를 하고, S.A를 작성하고, 깃헙 레포를 만들고, 에러를 해결하고 나니 뭔가 진이 빠져버렸다.. 오늘은 일찍 자고 내일부터 힘내보자.

최대공약수와 최소공배수

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

두 수의 최대공약수와 최소공배수를 반환한다.

fun solution(n: Int, m: Int): IntArray {
    var gcd = 0
    val lst = MutableList(0) { 0 }
    var notfound = true
    for (i in 1..sqrt(n.toFloat()).toInt()) {
        if (n % i == 0) {
            gcd = n / i
            if (m % gcd == 0) { notfound = false; break }
            lst.add(i)
        }
    }
    if (notfound) gcd = lst.last { m % it == 0 }
    return intArrayOf(gcd, n * m / gcd) }

최대공약수부터 구한다.
두 수가 나누어 떨어지는 가장 큰 수를 구하면 되는데, 성능을 위해서 n에 대해 제곱근까지만 탐색하고, n을 나누어 떨어지는 수의 짝이 되는 약수가 m을 나누어 떨어지는지 확인한다. 그렇다면 최대공약수를 구한 것이고, 아니라면 작은 약수를 배열에 저장해뒀다가 나중에 거꾸로 순회시킨다.

최대공약수를 구했다면 최소공배수는 n * m / gcd 이다.