프로그래머스 코딩테스트 Level 2. N개의 최소공배수 with Java

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12953

프로그래머스

 

풀이

import java.util.*;

class Solution {
    public int solution(int[] arr) {
        Arrays.sort(arr);
        
        for (int i=0; i<arr.length-1; i++) {
            int num = getGCD(arr[i+1], arr[i]);
            arr[i+1] = (arr[i] * arr[i+1]) / num;
        }
        
        return arr[arr.length - 1];
    }
    
    // 최대 공약수
    public static int getGCD(int n1, int n2) {
        if (n1 % n2 == 0) {
            return n2;
        }
        
        return getGCD(n2, n1%n2);
    }
}

1. 최소공배수: (n1 * n2) / n1과 n2 의 최소공약수

2. 최소공약수: 유클리드 호제법

3. 최대공약수를 활용해 탐색하며 마주하는 두 정수에 대해 최소공배수를 도출

 

 

https://github.com/yhyuk/h-algorithm/tree/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/2/12953.%E2%80%85N%EA%B0%9C%EC%9D%98%E2%80%85%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98

h-algorithm/프로그래머스/2/12953. N개의 최소공배수 at master · yhyuk/h-algorithm