프로그래머스 Lv2 N개의 최소공배수

문제 설명

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

제한 사항

• arr은 길이 1이상, 15이하인 배열입니다.
• arr의 원소는 100 이하인 자연수입니다.

입출력 예

arr	result
[2,6,8,14]	168
[1,2,3]	6

---

나의 풀이

문제를 접하자마자 떠올린 방법은 다음과 같다.

최소공배수를 구하기 위해 최대공약수를 구한다.

• 두 수 A, B에 대하여 최소공배수 = A * B / 최대공약수

최대공약수를 구하는 메서드를 만든 후 반복자 i에 대하여 (i < arr.length; i++)

answer = arr[0]과 arr[i]의 최대공약수를 먼저 구한 후 이를 통해 최소공배수를 구해answer에 저장한다.

• 처음부터answer를 arr[0]으로 설정하고 비교를 함으로써 반복자 i에 대한 조건을 쉽게 지킬 수 있다.

코드로 보면 다음과 같다

class Solution {
    public int solution(int[] arr) {
        int answer = arr[0];

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

        return answer;
    }

    // 1. 최대 공약수를 구하는 식 만들기

    public int gcd(int x, int y) {
        int gcd = 0;
        for (int i = x; i > 0; i--) {
            if (x % i == 0 && y % i == 0) {
                gcd = i;
                break;
            }
        }
        return gcd;
    }
}

내가 만든 gcd 메서드는 주어진 배열이 정렬이 되어있다고 가정했을 때, x 자신부터 비교하여 1씩 감소하는 형태로 최대공약수를 찾아가고 있다. 이는 O(logN)의 시간복잡도를 갖는다.

arr의 원소 길이와 원소의 범위가 비교적 크지 않았기에 위와 같은 시간복잡도를 갖는 메서드로도 충분히 해결을 할 수 있었다.

하지만 더 큰 범위의 테스트 케이스가 주어진다면?

이는 유클리드 호제법이라는 알고리즘을 통해 해결이 가능하다.

유클리드 호제법 풀이

유클리드 호제법이란?

두 양의 정수 a, b (a > b)에 대하여 a = bq + r ( 0 < r < b ) 이라 하면, a, b의 최대공약수는 b, r의 최대공약수와 같다. → gcd(a, b) = gcd(b, r)

예를 들어 1071과 1029의 최대공약수를 구한다고 하면,

• 1071은 1029로 나누어떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구함
  • 위의 변수를 차용하자면, r1 = 42
• 1029는 42로 나누어떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구함
  • r2 = 21
• 42는 21로 나누어 떨어진다 ( r2 % r1 == 0 )

따라서 최대공약수는 21가 되는 것이다.

이를 활용한 코드는 다음과 같다

class Solution {
        public int solution(int[] arr) {
        int answer = arr[0];

        for (int i = 0; i < arr.length; i++) {

            int gcd = gcd(answer, arr[i]);
            answer = answer * arr[i] / gcd;
        }
        return answer;
    }

    public static int gcd(int a, int b) {

        int x = Math.max(a, b);
        int y = Math.min(a, b);

        while (x % y != 0) {
            int r = x % y;
            x = y;
            y = r;
        }
        return y;
    }
}

보시다시피 내가 만든 gcd 메서드보다 훨씬 수행 속도가 빠르고 효율적임을 알 수 있다. 이는 유클리드 호제법의 시간복잡도가 O(logN)이기 때문이다!

평상 시에 이와 같은 최적화된 알고리즘들을 많이 익혀둔다면 코딩테스트에 많은 도움을 얻을 수 있을 것이다!

끄읕~