[프로그래머스 • 코틀린] [유클린드 호제법]최대공약수와 최소공배수 #12940

#12940

🎄 Question ?

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

class Solution {
    fun solution(n: Int, m: Int): IntArray {
        var answer = intArrayOf()
        return answer
    }
}

🧩 Thought Process

1. 최대 공약수 variable을 gcd(Greatest Common Divisor의 약자) 로 저장해주고 초기값을 1로 한다.
2. 최대공약수 찾기 가장 먼저 m이나 n 중 큰수를 작은수로 나누어보기 ! 나누어지면 작은 수가 최대공약수이다!
3. 만약 나누어지지 않는다면 작은 수의 값을 1씩 줄여가며 큰수를 나누어준다. 나누어 떨어지는 수가 최대공약수 !
4. 최소 공배수 variable 을 lcm(Least Common Multiple 의 약자)라고 둔고 초기값으로 1을 부여한다.
5. 각 m 과 n을 최대공약수로 나누어주고 lcm에 최대공약수를 곱해준다.
6. 최대 공약수의 값을 1씩 줄여가면서 이미 최대공약수로 나누어진 m과 n의 값을 나누어보고 둘다 공통으로 나누어지는 경우에는 m과 n의 값을 실제로 나누어주고 그 값을 lcm에 곱해준다.
7. 나누는 값이 2가 될때까지 나누어보고 남은 n과 m의 값을 lcm에 둘다 곱해주면 최소공배수를 찾을 수 있다!!
8. 최대공약수와 최소공배수를 intArray에 넣어 저장해주고 리턴한다!

import kotlin.math.*

class Solution {
    fun solution(n: Int, m: Int): IntArray {
        var gcd = 1
        var lcm = 1
        var N = n
        var M = m
        
        // 최대공약수 찾는 코드
        if (m%n == 0 || n%m == 0) {
            gcd = minOf(n, m)
        } else {
            for(i in 1 until minOf(n, m)-1) {
                if (maxOf(m, n)%(minOf(m, n)-i) == 0) {
                    gcd = minOf(n, m) - i
                    break
                } 
            }
        }
        // 최소 공배수 찾는 코드
        for (j in 0 until gcd) {
            if ((M % (gcd - j) == 0) && (N % (gcd - j) == 0)) {
                N /= (gcd - j)
                M /= (gcd - j)
                lcm *= (gcd - j)
            }
        }
        lcm = lcm*M*N
        
        return intArrayOf(gcd, lcm)
    }
}

테스트 대 실패 했당 25점이 모야...ㅜ

뭐가 잘못 된걸까... 흐음

another try:

import kotlin.math.*

class Solution {
    fun solution(n: Int, m: Int): IntArray {
        var answer = mutableListOf<Int>()

        if (n - m == 0) {
            answer.add(n)
        } else {
            var Max = maxOf(n, m)
            var Min = minOf(n, m)
            if (Max % Min == 0) {
                answer.add(Min)
            } else {
                for (i in 1 until Min) {
                    if (Max % (Min - i) == 0) {
                        answer.add(Min - i)
                        break
                }
            }
        }
        }
        answer.add(n*m/answer[0])
        return answer.toIntArray()
    }
}

minOf와 maxOf함수를 사용할 때 안 에 들어가는 값이 같은 경우를 따지지 않았어서 그 경우를 추가하니 에러가 줄었다. 그런데 여전히 만점이 안나왔다. 결국 답 확인...

🎀 Answer

해설 #1 유클리드 호제법 이용

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 간단 설명: 최대공약수 계산 법. n과 m의 최대공약수는 n을 m (n>m)으로 나누었을 때 의 나머지 r과 m의 최대공약수와 같다. 그 다음 m과 r의 최대공약수는 m을 r로 나눈 나머지와 r의 최대공약수와 같을 것이다.

// 두 값 a와 b를 인풋했을 때 최대공약수를 계산해주는 함수 정의
fun gcd(a: Int, b:Int): Int = if(b != 0) gcd(b, a % b) else a
// b가 0이 아닌 경우 함수 gcd가 반복되도록 짜여있다.

fun main(args : Array<String>) {
    var x = 4
    var y = 10
    println("최대 공약수 : ${gcd(x, y)}")
    println("최소 공배수 : ${x * y / gcd(x, y)}")

    x = 28
    y = 16
    println("최대 공약수 : ${gcd(x, y)}")
    println("최소 공배수 : ${x * y / gcd(x, y)}")
}

위 풀이를 응용해서 내 방식대로 문제를 풀이해보았다

class Solution {
    fun solution(n: Int, m: Int): IntArray {
        var answer = intArrayOf(gcd(maxOf(n, m), minOf(n, m)), n*m/gcd(maxOf(n, m), minOf(n, m)))
        return answer
    }
    
    fun gcd(a: Int, b: Int): Int = if(b != 0) gcd(b, a % b) else a
}

🎁 Result

https://github.com/eun-24k/Algorithm/blob/main/Programmers/kotlin/12940.kt

🏆 Comment

유클리도 호제법을 배웠다.

유클리드 호제법을 이용하지 않는 방법으로 문제를 풀어보려고 했는데 잘 되지 않았다. 다음에 기회되면 한번 시도해보면 좋을 거 같다.