프로그래머스 Lv.2) N개의 최소공배수

N개의 최소공배수

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

풀이

이 문제는 인터넷 검색을 통해 최대 공약수, 최소 공배수를 구하는 알고리즘을 찾았다. 평소같으면 몰라도 푸는 연습을 했겠지만, 이 문제는 찾고 이해하는게 더 좋다고 판단했기 때문이다. 분명 학부생 때는 이 알고리즘을 구현 했었다. 지금은 까먹었다는게 문제지만.. 아무튼 다시 한번 머리에 각인 시키는 계기가 되었으면 한다.

 

1. for문을 돌면서 최소공배수를 구한다.

2. 최소공배수는 두 숫자의 곱셈 / 두 숫자의 최대공약수 로 만든다.

3. 최대공약수를 구할 때는, 나눌 수 있을 때 까지 나눈 수를 구했다고 보면 된다.

 

코드

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;
    }
    
    private int gcd(int left, int right) {
        while(right !=0) {
            int mod = left%right;
            left = right;
            right = mod;
        }
        return left;
    }
    private int lcm(int left, int right) {
        return left*right/gcd(left,right);
    }
}