문제

정답 코드

class Solution {
    public int solution(int[] arr) {
        int leatCommonMultiple = arr[0];
        // 2개씩 최대공약수 구한다음 최소공배수 구하기
        if(arr.length>1) {
            for (int i = 0; i < arr.length - 1; i++) {
                leatCommonMultiple 
                		= doLeastCommonMultiple(leatCommonMultiple, arr[i + 1]);
            }
        }
        return leatCommonMultiple;
    }

    // 최대 공약수 구하기
    public int gcd(int a, int b) {
        if (b==0) return a;
        return gcd(b,a%b);
    }

    // 최소 공배수 구하기
    public int doLeastCommonMultiple(int a, int b) {
        return a*b/gcd(a,b);
    }
}

문제를 보자마자, 이건 최대공약수 구하는 공식을 알아야 풀 수 있겠다 싶어서 검색해봤다.

유클리드 호제법을 이용하여 GCD(Greatest Common Divisor)라는 방식으로 최대공약수를 구할 수 있었다.

( r은 (0 ≤ r < b) 이고, a ≥ b ) 일 때
두 수 a, b ∈ ℤ 이고, r = a mod b 이라고 한다. (r 은 a에 b를 나눈 나머지를 의미)
a 와 b의 최대공약수를 (a, b)라고 할 때 (a, b)의 최대공약수는 (b, r)의 최대공약수와 같다.

• GCD(a, b) = GCD(b, r)

예로 하나 들어보자. 두 수 581, 322 가 있다고 가정해보자.
GCD(581, 322) = GCD(322, 259) = GCD(259, 63) = GCD(63, 7) = GCD(7, 0) = 7
결과적으로 나머지가 없다는 것은 공통된 약수로 나누어 떨어진다는 의미이므로 7이 최대공약수가 된다.
출처: https://st-lab.tistory.com/154

처음엔 이해가 가지 않았는데, 증명 과정을 보니 이해가 되었다.
(고등학생 때 사용하던 귀류법도 새록새록 기억나니 좋았다)

따라서 최대공약수와 최소공배수를 구하는 함수를 만든 뒤,
앞에서부터 두개의 숫자씩 최소공배수를 구해주어 N개의 숫자의 최소공배수를 return했다.

다른 사람 풀이

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

        while (check) {
            answer++;
            for (int i = 0; i < arr.length; i++) {
                if (answer % arr[i] != 0) {
                    check = true;
                    break;
                } else {
                    check = false;
                }
            }
        }

        return answer;
    }
}

스터디 팀원분께서 가져온 풀이..!!

공배수란 arr에 들어있는 모든 숫자로 나눴을 때 나머지가 0이 되는 숫자이다.
그 중에서 가장 작은 숫자가 최소공배수이므로 answer를 1씩 더하며 확인.

GCD를 사용하지 않고도 이렇게 간단히 풀 수 있는 방법이 있구나!
눈이 뜨인다. 대단하다. 나는 왜 이렇게 안될까
나는 야 거북이이이 노오오력하여라