💡 문제
두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.
⚠️ 제한사항
- arr은 길이 1이상, 15이하인 배열입니다.
- arr의 원소는 100 이하인 자연수입니다.
✅ 풀이
👆 첫 번째 풀이 (실패)
- arr들의 최대 공약수를 한 번에 구하고자 했다.
- arr 중 가장 큰 수부터 1까지의 수 중에서 arr의 모든 숫자들을 나눴을 때 나머지가 0인 공약수를 찾았다.
- 구한 공약수로 arr의 모든 숫자들을 나눠주고, 공약수를 곱해 공배수를 구했다.
class Solution {
fun solution(arr: IntArray): Int {
var max = arr.maxOrNull() ?: 100
var gcd = (max downTo 1).first { n -> arr.all { it % n == 0 } }
return arr.fold(gcd) { total, n -> total * n / gcd }
}
}나는 처음에 뭐가 문제인지 몰랐다. 테스트케이스는 통과하지만 채점을 받으면 0점이 나왔다... 여러 수의 최소 공배수는 이런 식으로 구하는 게 아니라고 한다. 반례를 살펴보면, 다음과 같다.
나의 방식에 따르면, [2, 4, 6, 8]의 전체 최대 공약수는 2가 되고 이걸 이용해 (최소가 아닌) 최소 공배수를 구하면 2 * (1 * 2 * 3 * 4)가 되어 48이 된다.
여러 수의 최소 공배수는 그럼 어떻게 구하는 것일까. 한 번에 구하려고 하지 말고 2개씩 차근차근 구하면 된다. 예를 들어, 2와 4의 최소 공배수를 구하고, 구한 최소 공배수와 6의 최소 공배수를 구하면 되는 식이다.
✌️ 두 번째 풀이 (성공)
괜히 꼼수 부리려다 0점을 받은 것 같아 이번에는 차근차근히 풀어보았다. arr의 0번째 수부터 차근차근 최소 공배수를 구했더니 드디어 풀이에 성공했다. 최소 공배수를 구할 때는 두 수의 곱은 두 수의 최소 공배수와 최대 공약수의 곱과 같다는 공식을 이용해주었다.
class Solution {
tailrec fun gcd(x: Int, y: Int): Int = if (x % y == 0) y else gcd(y, x % y)
fun solution(arr: IntArray): Int {
// lcm = (X * Y) / gcd
var answer = arr[0]
(1..arr.size-1).map {
answer = answer * arr[it] / gcd(answer, arr[it])
}
return answer
}
}🔥 다른 사람의 풀이
나는 최소공배수 * 최대공약수 = X * Y라는 공식에서 벗어나지 못했는데, 다른 방법으로 풀이한 사람도 있었다. 가져온 풀이는 answer를 1씩 키워가면서, arr의 모든 수들로 나누어 떨어지는 가장 작은 수를 찾는 방식으로 풀이했다. 공약수를 구하지 않고 공배수만 구한 풀이라서 문제에 더 알맞은 풀이 같다는 생각을 했다.
class Solution {
fun solution(arr: IntArray): Int {
var answer = 1
while(true) {
var x = 0
for(a in arr) x += answer%a
if(x==0) return answer
answer++
}
return answer
}
}💭 후기
다른 사람의 풀이를 보고, 내가 첫 번째 풀이에서 조금만 생각을 바꿨다면 굳이 최대 공약수를 구하지 않고 풀 수 있었을텐데 라는 생각이 들었다. 모든 수의 공약수를 구하는 게 아니라 모든 수의 공배수를 구하면 됐었는데, 생각을 확장시키지 못한 게 좀 아쉬웠다. 풀이 중에 한 방식에 꽂히면 그 방식만 죽어라 파는 습관을 고쳐야겠다. 애초에 여러 개 생각해놓고 적합한 방식을 고르는 연습도 하면 좋을 것 같다.
