[Lv.2] 프로그래머스 - N개의 최소공배수 : Java

프로그래머스

 

 

 

이해하기

처음에는 [2, 6, 8, 14]의 예제를 가지고 풀어보았다.

4개의 숫자의 최대공약수는 2이기에 각각을 2로 나눈 값인 [1, 3, 4, 7]을 곱한 값에 2를 곱해주었더니 result값이 나왔다.

이것만 생각하고 문제를 풀었는데 줄줄이 뜨는 실패...

 

혹시 싶어서 [2, 4, 7]을 가지고 풀어보았는데 왜 실패했는지 이해가 됐다.

2, 4, 7의 최소공배수는 28이고, 이는 전체를 곱한 값에서 2와 4의 최대공약수인 2로 나눈 값이었다.

 

참고한 블로그⬇️

[Java/자바] 프로그래머스 Lv2 - N개의 최소공배수 (유클리드 호재법)

 

[2, 4, 7]을 가지고 다시 한 번 풀이해보면 다음과 같다.

• 먼저 2, 4만 가지고 최소공배수를 찾는다.
  • 최소공배수 = 2 * 4 / 최대공약수
• 그 다음으로 위에서 구한 값인 4와 7의 최소공배수를 찾는다.
• 이걸 배열 끝까지 반복한다!

 

 

문제풀이

class Solution {
    public int solution(int[] arr) {
        int answer = arr[0];
        
        for (int i = 1; i < arr.length; i++) {
            answer = lcm(answer, arr[i]);
        }
        
        return answer;
    }
    
    public int gcd(int a, int b) {
        if (a % b == 0) {
            return b;
        }
        
        return gcd(b, a % b);
    }
    
    public int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }
}

 

전체의 최대공약수를 찾으려고 했던게 실패의 원인...! 다음부터 실수하지 않도록 기록해둔다!