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

문제

https://programmers.co.kr/learn/courses/30/lessons/12953/solution_groups?language=java 

프로그래머스

 

풀이

단순히 두 숫자의 최소 공배수를 구하는게 아닌 여러 숫자의 최소공배수를 구할 수 있는지를 물어보는 문제다.

 

우선 두 숫자 a, b의 최소공배수는 다음과 같다.

 

int getLCM(int a, int b) {
	return a * b / getGCD(a, b)
}

즉 a, b의 최소공배수는 a*b / 최소공약수와 같다.

 

그럼 두 숫자가 아닌 3개 이상 숫자의 최소공배수의 공식은 무엇인가?

예를들어 숫자 a, b, c의 최소공배수를 구한다고 하자.

1. a와 b의 최소공배수를 구한다. 구한 최소공배수를 k라고 하자.

2. k와 c의 최소공배수를 구한다.

 

즉. 구한 최소공배수와 다음 숫자의 최소공배수를 구하면된다.

주의할점

최소공배수를 구할 때는 최대공약수를 구해야되는데 최대공약수 구하는 함수에서 반드시 a가 b보다 크거나 같아야 한다는 것을 기억하자.

 

// a, b 최대공약수 구하는 함수(a>=b)

int getGCD(int a, int b){
	while(b != 0){
    	int r = a%b;
        a = b;
        b = r;
    }
    return a;
}

 

코드

package 프로그래머스.레벨2.N개의최소공배수.첫풀이;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

/*
* a, b의 최소 공배수 =  a * b / 최대 공약수
* a, b,c의 최소 공배수 = a,b의 최소 공배수 * b /
* */
public class Solution {
    public int solution(int[] arr) {
        int answer = 1;

        for (int i=0; i<arr.length; i++) {
            answer = lcm(answer, arr[i]);
        }

        return answer;
    }

    // 최대공약수 공식
    static int gcd(int a, int b) {
        while(b !=0) {
            int r = a%b;
            a = b;
            b = r;
        }
        return a;
    }

    // 최소공배수 공식
    static int lcm(int a, int b) {
        if (b > a) {
            int temp = a;
            a = b;
            b = temp;
        }

        return a * b / gcd(a, b);
    }

    @Test
    void test() {
        Assertions.assertEquals(168, solution(new int[]{2, 6, 8, 14}));
        Assertions.assertEquals(6, solution(new int[]{1, 2, 3}));
    }
}