N개의 최소공배수

· 문제 설명

두 수의 최소공배수(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

 

---

· Thinking 1

만약, [15, 20, 30] 이 들어왔다.

1. 15와 20의 최대공약수를 구한다. = 5
2. 이 결과로 나온 5와 30의 최대공약수를 구한다 = 5

최소 공배수 구하기
1. 15 와 20의 최소공배수를 구한다. = 60
2. 60과 30의 최소공배수를 구한다. = 60

 

최소 공배수를 구하려면은 최대 공약수가 필요해 
최소 공배수가 = a * b / gcd(a,b의)

1. 15와 20의 최대 공약수를 구하고 : 5
2. 15와 20의 최소 공배수를 구한다. : 60
3. 5와 30의 최대 공약수를 구하고
4. 60과 30의 최소 공배수를 구한다.

int small = arr[0];
int big = 0;
int temp = 0;
int lcm = 0;

for (int i = 1; i < arr.length; i++) {
	System.out.print(small + "과 " + arr[i] + "의 최대 공약수 : ");
	while (small != 0) {
		int nmg = arr[i] % small;
		big = small; // 최대공약수
		small = nmg;
	}
	small = big;
	System.out.println(big);

	if (i == 1) {
		lcm = arr[i - 1] * arr[i] / big;
		temp = lcm;
		System.out.println(arr[i-1] + "과 " + arr[i] + "의 최소 공배수 : " + lcm);
	} else {
		System.out.print(temp + "과 ");
		temp = (temp * arr[i]) / big;
		System.out.println(arr[i] + "의 최소 공배수: " + temp);
	}
}

생각을 잘못했네..

최소 공배수는 두 수의 최소 공약수로 나누는것..
나는 지금 계속 잘못하고 있었음.. 아 울고싶다 ㅠ

---

· 완성 코드

import java.util.Arrays;

class Solution {
  public  int solution(int[] arr) {
	Arrays.sort(arr);
	int lcm = arr[0] * arr[1] / gcd(arr[0], arr[1]);
		
	for (int i = 2; i < arr.length; i++) {
		lcm = lcm * arr[i] / gcd(lcm, arr[i]);
	}
		
	return lcm;
  }
	
  public static int gcd(int small, int big) {
	while (small != 0) {
		int nmg = big % small;
		big = small;
		small = nmg;
	}
	return big;
  }
}

문제를 통과하긴 했는데 자괴감든다..
밥을 안먹어서 머리가 안돌아간걸까..

이게 뭐라고 이 문제를 푸는데 너무 오래걸린 나 자신한테 짜증나고...................

---

· 문제 출처

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

알고리즘 연습 - N개의 최소공배수 | 프로그래머스