프로그래머스 - 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

나의 풀이

import java.util.Arrays;
class Solution {
    public int solution(int[] arr) {
        int answer = 0;
        Arrays.sort(arr);
        for(int i = 0; i < arr.length-1; i++){
            int maxG = 0;
            int minL = 0;
            for(int j = 1; j <= arr[i]; j++){
                if(arr[i]%j == 0 && arr[i+1]%j==0){
                    if(maxG < j){
                        maxG = j;
                        minL = arr[i+1]/j * arr[i];
                    }
                }
            }
            arr[i+1] = minL;
            Arrays.sort(arr);
            answer = arr[i+1];
        }
        return answer;
    }
}

돌아보기

우선 백준에서 풀었던 해법을 참고했다.
예전에는 이런걸 풀었는데 접근 방법을 생각못하다니..침울..

유클리드호제법

를 알 필요가 있었다.

최소공배수, 최대공약수와 유클리드 호제법

• LCM : 최소공배수
• GCD : 최대공약수
  두 수의 최소공배수 : LCM = (a*b) / GCD

---

유클리드 호제법

두 수 a,b ( a > b) 에 대하여
a % b = 0 일 경우 GCD = b
a % b = c 일 경우
b % c = 0 이 될 때 까지 반복한다.

코드 구현

class Uclid{
	public long gcd(int a, int b){
    	if(a > b){
        	return (a % b == 0) ? b : gcd(b, a % b);
        }
        else {
        	return (b % a == 0) ? a : gcd(a, b % a);
        }
    }	
}

그리고 테스트 케이스 하나가 틀렸다고 나왔는데 계산 범위가 int형을 넘어가서 생긴 문제였다.
그래서 마지막에 나누기를 먼저 한 후, 곱해주니 문제가 해결되었다.
처음부터 long으로 문제를 풀면 될 일이었다.
유념하자

출처 : 프로그래머스