[Java] 연습문제 - N개의 최소공배수 (Lv2)

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

프로그래머스

 

 

✔ 입출력 예시

N개의 최소공배수 입출력 예시

 

 

💡 포인트

1️⃣ 최대공약수를 구하는 알고리즘 : 유클리드 호제법

      https://ichijeochi.tistory.com/538?category=1012068

2️⃣ 최소공배수 = 최대공약수를 구하고자하는 모든 수의 곱 / 최대공약수

3️⃣ 최대공약수와 최소공배수의 크기가 클 수 있기 때문에 int가 아닌 long 타입을 사용

 

 

❓ 풀이방법

     예시에는 나와있지 않은 테스트 케이스를 이용

     ex) int[] arr = {4, 5, 9, 12}

     1️⃣ GCD(5, 4, 0)

           multiple은 모든 수의 곱을 구하기 위해 초기값을 1로 설정

           첫 최대공약수를 구할 때는 gcd변수를 구해준 최대공약수로 초기화하고 multiple은 현재의 두 수를 모두 곱해줌

 

     2️⃣ GCD(20, 9, 1)

           이전에 구한 최소공배수와 새로운 수 (arr[2])와의 최대공약수를 구해줌

          gcd가 0이 아닐 때는 첫 최대공약수가 아니므로 현재 단계에서 구해준 최대공약수를 곱해줌

          multiple 역시 이전의 multiple에 현재 단계에서 비교한 수(arr[2])를 곱해줌

 

     3️⃣ GCD(180, 12, 1)

           숫자를 담은 배열 arr의 마지막까지 이와 같은 방법을 반복하다보면 모든 수의 최대공약수를 구할 수 있음

           👉 최종값으로 gcd = 12, multiple = 180 * 12 = 1728이므로 결과는 multiple / gcd = 1728 / 12 = 144

 

 

❗ 결과

   👉 테스트 통과

 

 

✔ 소스코드

 

import java.util.Arrays;

public class Solution { // N개의 최소공배수

	public static void main(String[] args) {
//		int[] arr = { 2, 6, 8, 14 };
//		int[] arr = {1, 2, 3};
		int[] arr = {3, 4, 9, 16};

		System.out.println(solution(arr));
	}

	private static int solution(int[] arr) {
		int answer = 0;
		long gcd = 0;  // 최대공약수
		long multiple = 0;  // 모든 수의 곱
		
		Arrays.sort(arr);  // 유클리드 호제법을 이용하기 위해 (작은 수와 큰 수 구별 위해)
		
		// 최대공약수 구하기 (유클리드 호제법)
		for(int i = 1;i < arr.length; i++) {
			if(gcd == 0) {  // 처음으로 최대공약수를 구할 때
				gcd = GCD(arr[i], arr[i-1], gcd);
				multiple = arr[i] * arr[i-1];
			} else {  // 이전에 구한 최대공약수가 존재할 때
				gcd *= GCD(multiple/gcd, arr[i], gcd);
				multiple *= arr[i];
			}
		}
		
		answer = (int)multiple/(int)gcd;
		
		return answer;
	}

    // 유클리드 호제법
	private static long GCD(long a, long b, long gcd) {
		if(b == 0) {
			gcd = a;
			return gcd;
		} else {
			return GCD(b, a%b, gcd);
		}
	}
}

최대공약수를 구하는 법은 유클리드 호제법을 기억해내서 쉬웠지만 최소공배수까지 생각하려니까 은근 헷갈렸던 문제였다.