문제 설명
두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.
제한 사항
- 두 수는 1이상 1000000이하의 자연수입니다
내 풀이
import kotlin.math.*
class Solution {
fun solution(n: Int, m: Int): IntArray {
var range = max(n,m)
var maxDivideNumber = 0
var minDivideNumber = 1
for(i in 1 .. range){
if(n % i == 0 && m % i ==0)
maxDivideNumber = i
}
while(minDivideNumber>0){
if(minDivideNumber % n ==0 && minDivideNumber % m ==0){
break
}
minDivideNumber ++
}
var answer = intArrayOf(maxDivideNumber,minDivideNumber)
return answer
}
}그냥 반복문으로 구해줬당
최대 공약수는
n이랑m 중에 큰수를 for문이 돌 범위로 지정해주고,
n이랑 m을 i로 나눠서 둘다 나누어떨어지는 수를 maxDivideNumber에 계속 초기화해서 넣어줌 ㅋㅋ
그냥 생각해도 효율적이지 않은 느낌이 드는데,, 그냥 함..
그리고 최소공배수는 while문으로 minDivideNumber가 0보다 클때 반복을하게 해주고
minDivideNumber 가 n이랑 m으로 둘다 나누어떨어지는 수일때 반복문을 탈출하게해줬다.
더 효율적으로 할 수있는 방법이 있을텐데……
멀라….
다른 사람 풀이
다른 사람 풀이를 보니깐
최대공약수는 gcd 라고 부르고
최소공배수는 lcm이라고 부르나봄!
최대공약수 GCD(Greatest Common Divisor)
최소공배수 LCM(Lowest Common Multiple)
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)
}
일단 딱 보니까 최대공약수만 구하면 최소공배수는 그냥 따로 안구하고 n , m , 최대공약수만으로도 구해지는 공식이 있나보다.
n*m / 최대공약수 =최소공배수 인가봄 ㅋㅋ
이런 공식은 어케 알고있는거지?
몰랐다가 그냥 당연하게 생각해보면 추론되어야하는건가?
수학이랑 너무 안친하게살아와서 모르겠음.
이 분은 뭔가 최대공약수도 쌈박하게 구하심
tailrec 이라는 키워드를 처음 봐서 검색해보니까 재귀함수라는 거였당
재귀함수도 처음봤는데 함수가 자기자신을 다시 호출해서 작업을 수행하는 방식이라고함
반복문을 쓰지않고 반복을 할 수 있다고함..
그냥 반복문 쓰면 안되나요? .. ㅜ.ㅜ
아무튼 그래서 숫자를 넣으면 b 가 0이면 a를 리턴하고,
0이 아니라면, a자리에 b를 넣어주고, a를 b로 나눈 나머지를 b자리에 넣어서 다시 gcd함수를 호출하는 방식인데,
찾아보니까 이게 유클리드 호제법 이라는 공식?을 사용해서 최대공약수와 최소공배수를 구하는 방법인가봄.. 유클리드가 누군데요~ 유클리드… ? 클리드는 아는데..
