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

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

 

소요시간 : 37분

 

gcd랑 lcm 까먹어서,,

유클리드 호제법 보느라 오래걸렸다....

그런데 여기서 포인트는

배열을 sort하여 제일 큰 수와 그 다음 큰 수부터 최소공배수를 구해줘야 편하다.

그래야 큰 값을 함수 매개변수 첫번째로 바로 줄 수 있기 때문.

 

func 가 gcd 구하는 함수

func2 가 lcm 구하는 함수.

배열 크기가 1보다 크다면 0번쨰와 1번째 수의 lcm을 먼저 구하고

그 값을 func2의 첫번째 매개변수로 준다.

fun2의 두번째 매개변수는 arr의 다음 인덱스 값.

이걸 arr 끝까지 반복하면 정답이 나온다.

 

수학을 다 까먹어버려서 나름 어려웠다.

import java.util.Arrays;

class Solution {
    public int solution(int[] arr) {
    	if(arr.length == 1) return arr[0];
    	
    	Arrays.sort(arr);
        
    	int answer = func2(arr[arr.length-1], arr[arr.length-2]);
    	for (int i = arr.length-3; i >= 0; i--) {
    		answer = func2(answer, arr[i]);
        }
        
        return answer;
    }
    
    int func2(int a, int b) {
    	return (a*b) / func(a, b);
    }
    
    int func(int a, int b) {
    	if(b == 0) return a;
    	return func(b, a % b);
    }
}