코딩 테스트/Level 2

31. N개의 최소공배수

컴닥 2020. 8. 15. 10:22
반응형

https://programmers.co.kr/learn/courses/30/lessons/12953

N개의 최소공배수
연습문제
3631명 완료

유클리드 호제법 참고

https://comdoc.tistory.com/entry/%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98-%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98

 

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

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배��

programmers.co.kr

def solution(arr):
    for i in range(len(arr) - 1):
        arr[i + 1] = lcm(arr[i], arr[i + 1])
    return arr[-1]  # arr[len(arr) - 1]


def lcm(a, b):
    return (a * b) / gcd(a, b)


def gcd(a, b):
    mod = a % b
    while mod > 0:
        a, b = b, mod
        mod = a % b
    return b

math.gcd를 이용해서 줄여 보겠습니다. 

from math import gcd


def solution(arr):
    for i in range(len(arr) - 1):
        arr[i + 1] = int((arr[i] * arr[i + 1]) / gcd(arr[i], arr[i + 1]))
    return arr[-1]

함수형으로... 

from math import gcd
from functools import reduce


def solution(arr):
    return reduce(lambda a, b: int(a * b / gcd(a, b)), arr)

 

Java

class Solution {
    public int solution(int[] arr) {
        for (var i = 0; i < arr.length - 1; i++)
            arr[i + 1] = lcm(arr[i], arr[i + 1]);
        return arr[arr.length - 1];
    }

    int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }

    int gcd(int a, int b) {
        int temp;
        while (b != 0) {
            temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }
}

함수형으로.. 

import java.util.Arrays;

class Solution {
    public int solution(int[] arr) {
        return Arrays.stream(arr).reduce(this::lcm).getAsInt();
    }

    int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }

    int gcd(int a, int b) {
        int temp;
        while (b != 0) {
            temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }
}

옵셔널을 안쓰면 경고가 뜨는데... 

import java.util.Arrays;

class Solution {
    public int solution(int[] arr) {
        var optional = Arrays.stream(arr).reduce(this::lcm);
        return optional.isPresent()? optional.getAsInt() : 0;
    }

    int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }

    int gcd(int a, int b) {
        int temp;
        while (b != 0) {
            temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }
}
반응형