[12953] N개의 최소공배수

✔ N개의 최소공배수

[프로그래머스 12953]

문제 분석하기

answer을 배열의 첫 번째 값으로 갱신한 후, 배열을 차례대로 탐색하며 최소공배수로 갱신하여 반환

손으로 풀어보기

1. answer을 배열의 첫 번째 값으로 갱신
2. 배열의 두 번째부터 탐색하며 answer과의 최소공배수로 answer을 갱신
3. answer 반환

슈도코드 작성하기

arr(n개의 숫자를 담은 배열)
answer(arr의 최소공배수) = arr[0]
for(i -> 1부터 arr만큼) {
    answer = answer * arr[i] / 최대 공약수 함수(answer, arr[i])
}
answer 반환

최대 공약수 함수 {
    a(n과 m 중 큰 수)
    b(n과 m 중 작은 수)
    if(b가 0이라면)
        a가 최대 공약수
    else
        최대 공약수 함수(작은 수, 큰 수 % 작은 수)
}

코드 구현하기

/**
 * 12953) N개의_최소공배수
 */
public class L022_12953 {
    // arr(n개의 숫자를 담은 배열)
    public int solution(int[] arr) {
        // answer(arr의 최소공배수) = arr[0]
        int answer = arr[0];
        // 배열의 두 번째부터 탐색하며 answer과의 최소공배수로 answer을 갱신
        for (int i = 1; i < arr.length; i++) {
            // answer = answer * arr[i] / 최대 공약수 함수(answer, arr[i])
            answer = answer * arr[i] / gcd(answer, arr[i]);
        }
        // answer 반환
        return answer;
    }

    // 최대 공약수 함수
    private int gcd(int n, int m) {
        // a(n과 m 중 큰 수)
        int a = Math.max(n, m);
        // b(n과 m 중 작은 수)
        int b = Math.min(n, m);
        // b가 0이라면
        if (b == 0)
            // a가 최대 공약수
            return a;
        else
            // 최대 공약수 함수(작은 수, 큰 수 % 작은 수)
            return gcd(b, a % b);
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L022_12953 solution = new L022_12953();

        int[] arr = { 2, 6, 8, 14 };

        int result = solution.solution(arr);

        System.out.println(result);
    }
}