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

문제

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

코딩테스트 연습 - N개의 최소공배수

 

풀이

약수, 배수, 공배수, 최소공배수, 최대공약수

• 약수(divisor) : 어떤 정수를 나누어 떨어지게 하는 0이 아닌 정수
• 배수(multiple) : 어떤 정수의 몇 배가 되는 수. (정수a가 정수b로 나뉘어질 때, a는 b의 배수이다)
• 공약수(common divisor) : 2개 이상의 수의 공통인 약수
• 공배수(common multiple) : 2개 이상의 수의 공통인 배수
• 최대공약수(greatest common divisor) : 2개 이상의 수의 공약수 중에서 최대인 수
• 최소공배수(leastest common multiple) : 2개 이상의 수의 공배수 중에서 최소인 수.

 

최대공약수 문제 팁

• 두 수 a, b의 최대공약수는 b와 (a를 b로 나눈 나머지 값)의 최대공약수와 같다.
• 최대공약수(a, b) == 최대공약수(b, a%b)
  
  
• 두 수 a, b에 대해서
  a는 b의 값으로, b는 a를 b로 나눈 나머지 값으로 갱신하는 걸 반복한다. (~나머지 값으로 갱신된 b가 0이 될때까지)

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

 

최소공배수 문제 팁

• 두 수 a, b의 최소공배수는 두 수를 곱한 값을 최대공약수로 나눈 값이다.
• 최소공배수(a, b) == (a*b / 최대공약수(a, b))

public int lcm(int a, int b) {
    return (a * b / gcd(a, b));
}

 

코드

class Solution {
    public int solution(int[] arr) {
        int lcm = arr[0];
        
        // 앞서 구해진 최소공배수와 새로운 값 간의 최소공배수 구하기
        for (int i = 1; i < arr.length; i++) {
            // 최대공약수
            int gcd = gcd(lcm, arr[i]);
            // 최소공배수 = 두 수의 곱 / 최대공약수
            lcm = (lcm * arr[i] / gcd);
        }
        
        // 마지막으로 구해진 최소공배수 반환
        return lcm;
    }
    
    public int gcd(int a, int b) {
        while (b != 0) {
            // 나머지 값
            int r = a % b;

            // gcd(a, b) == gcd(b, r)
            a = b;
            b = r;
        }

        return a;
    }
}