[프로그래머스] 11053 N개의 최소공배수 - JAVA

[프로그래머스] 11053 N개의 최소공배수 - JAVA

문제

https://www.acmicpc.net/problem/14939

문제 분석

조건

• `arr`: 길이 1 이상 15 이하의 정수 배열
• 각 원소는 1 이상 100 이하의 자연수
• 배열에 주어진 모든 수의 최소공배수를 구해라

풀이방법

• 두 수의 최소공배수는 아래 공식을 사용해서 구할 수 있다.
  • `LCM(a, b) = (a * b) / GCD(a, b)`
•  GCD는 유클리드 호제법으로 구할 수 있음
• 배열의 최소공배수는 순차적으로 두 수씩 계산해 나가면 된다

코드

class Solution {
    public int solution(int[] arr) {
        int answer = 1;
        int size = arr.length;
        for (int i = 0; i < size; i++) {
            answer = (answer * arr[i]) / gcd(answer, arr[i]);
        }
        return answer;
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }
}