[프로그래머스] [Kotlin] [Level2] N개의 최소공배수

코딩테스트 연습 - N개의 최소공배수

프로그래머스

문제 설명

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

 

제한사항

• arr은 길이 1 이상, 15 이하인 배열입니다.
• arr의 원소는 100 이하인 자연수입니다.

 

시도

private fun gcd(a: Int, b: Int): Int = if (b != 0) gcd(b, a % b) else a

private fun lcm(a: Int, b: Int) = a * b / gcd(a, b)

fun solution(arr: IntArray): Int {
    var answer = arr[0]
    arr.forEach { answer = lcm(answer, it) }
    return answer
}

성능요약: 메모리: 61.4 MB, 시간: 0.03 ms

 

접근

최대 공약수 찾기

private fun gcd(a: Int, b: Int): Int = if (b != 0) gcd(b, a % b) else a

이 함수는 두 개의 정수 a, b의 최대공약수를 찾는 함수이고, 유클리드 알고리즘을 사용하여 구현되어 있다.

유클리드 알고리즘은 2개의 자연수 a, b에 대해(a>b) a를 b로 나눈 나머지를 r이라 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 성질을 이용한 것이다.

• 두 숫자 a와 b를 받아서, 만약 b가 0이 아니라면, gcd 함수를 다시 호출한다. 이때, a 대신 b를 넣고, b 대신에 a를 b로 나눈 나머지를 넣는다.
• 이 과정을 재귀적으로 반복한다.
• 만약 b가 0이라면, a를 반환한다. 이 a가 바로 두 숫자의 최대공약수이다.

예시로 a가 48이고 b가 18인 `gcd(48, 18)`을 호출하면,

`gcd(48, 18)`은 b가 0이 아니므로 `gcd(18, 48 % 18)`를 호출 ➜ `gcd(18, 12)`
`gcd(18, 12)`은 b가 0이 아니므로 `gcd(12, 18 % 12)`를 호출 ➜ `gcd(12, 6)`
`gcd(12, 6)`은 b가 0이 아니므로 `gcd(6, 12 % 6)`를 호출 ➜ `gcd(6, 0)`
`gcd(6, 0)`은 b가 0이므로 a인 6을 반환

: 최대공약수는 6

 

최소공배수 찾기

private fun lcm(a: Int, b: Int) = a * b / gcd(a, b)

이 함수는 두 정수 a와 b의 최소공배수를 찾는 함수이다. 두 수의 곱을 두 수의 최대공약수로 나누면 최소공배수를 얻을 수 있다.

• 이 공식은 두 수의 곱이 그 두 수의 최대공약수와 최소공배수의 곱과 같다는 수학적 원리에 기반한 것이다.
• a * b = gcd(a, b) * lcm(a, b)
• 따라서 이 관계를 통해 두 수의 최소공배수는 두 수의 곱을 두 수의 최대공약수로 나누어 계산할 수 있다.

 

N개 숫자들의 최소공배수 찾기

fun solution(arr: IntArray): Int {
    var answer = arr[0]
    arr.forEach { answer = lcm(answer, it) }
    return answer
}

• 먼저 `answer`라는 변수를 선언하고, 이를 arr의 첫 번째 요소로 초기화한다. 이 `answer`는 현재까지의 최소공배수를 저장하는 변수로 사용된다.
• `arr.forEach { answer = lcm(answer, it) }`는 arr 배열의 각 요소에 대해, 현재의 `answer`와 그 요소의 최소공배수를 계산하고, 그 결과를 다시 `answer`에 저장한다. 이를 통해 배열의 모든 요소에 대한 최소공배수를 계산한다.

 

 

 

언제나 잘못된 설명이나 부족한 부분에 대한 피드백은 환영입니다🤍