프로그래머스 N개의 최소공배수 (Level2 Java)

https://school.programmers.co.kr/learn/courses/30/lessons/12953?language=java

프로그래머스

---

문제

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

제한 사항
arr은 길이 1이상, 15이하인 배열입니다.
arr의 원소는 100 이하인 자연수입니다.
입출력 예
arr result
[2,6,8,14] 168
[1,2,3] 6

---

문제 해결을 위한 과정

처음에는 배열의 가장 큰 수(max)부터 시작해서 (int)1e9 즉 (10억)까지 숫자를 1씩 더하며 모든 원소로 나누어떨어지는지 확인하는 완전 탐색 방식으로 접근할 수 있습니다. 하지만 이 방식은 수의 규모가 커지면 시간 초과(TLE)의 위험이 있습니다.

따라서 정수론의 유클리드 호제법(최대공약수 구하기 공식)을 결합하여, 두 개씩 차례대로 최소공배수를 누적해 나가는 수학적 방식으로 해결했습니다.

1. 누적 연산 설계: 배열의 첫 번째 원소(arr[0])를 시작 정답으로 둡니다.
2. 배열 순회: 반복문을 돌며 현재까지 구한 누적 최소공배수(answer)와 다음 원소(arr[i])의 새로운 최소공배수를 구하여 answer를 갱신합니다.
3. 최소공배수 공식 활용: 두 수 A, B의 최소공배수는 (A * B) / 최대공약수(GCD)라는 수학적 공식이 성립하므로, 유클리드 호제법으로 최대공약수를 구한 뒤 대입합니다.
4. 이 과정을 배열의 끝까지 반복하면 n개 전체의 최소공배수를 구할 수 있습니다.

---

소스코드

import java.util.*;

class Solution {
    public int solution(int[] arr) {
        int answer = arr[0];
        
        for (int i = 1; i < arr.length; i++) {
            answer = getLcm(answer, arr[i]);
        }
        
        return answer;
    }
    
    private int getGcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return getGcd(b, a % b);
    }
    
    private int getLcm(int a, int b) {
        return (a * b) / getGcd(a, b);
    }
}