Lv.2 : N개의 최소공배수

👉 문제링크

프로그래머스

---

---

🔸 문제 분석 🔸

• n개의 자연수에 대한 최소공배수를 반환한다.

🔸 문제 풀이 🔸

• a, b 두 수의 최소공배수는 'a * b / (a와 b의 최대공약수) ' 공식을 이용한다.
• 1번째 원소와 2번째 원소의 최소공배수를 구하고, 그 값을 3번째 원소와 최소공배수를 구하며 n번째까지 반복하면 n개의 자연수에 대한 최소 공배수를 구할 수 있다.

---

🔸 코드 🔸

import java.util.Arrays;

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

🔸 코드 해석 🔸

• 위의 공식대로 최소공약수를 구한다.
• 최대공배수는 유클리드 호제법을 이용해서 구한다.

---

🔸 end 🔸

• • n개의 자연수가 최대 100이지만, 15개 모두 소인수로 이루어져 있다면 long의 범위도 벗어날 수 있어보였다.
  • 하지만, 이 문제에선 그런 테스트 케이스는 넣어두지않아서 long도 아닌 int로만 해도 충분히 통과되었다
    • 반환값이 long이 아닌 int여서 알 수 있었다.