[Programmers - lv02] N개의 최소공배수 (cpp / python)

N개의 최소공배수

프로그래머스

 

문제 설명

N개의 숫자가 주어질 때 모든 수의 최소공배수를 구하는 문제

$$
G\, is\, Greate\, Common\, Divsor(최대공약수)\\
L\, is\, Least\, Common\, Multiple(최소공배수)\\
...\\
G \times L = A \times B \\
L = A \times B \div G \\
...\\
a와\, b는\, disjont(서로소)\\
A = a \times G \\
B = b \times G \\
$$

위와 같은 수학 공식을 이용하여 문제를 해결한다.

문제 풀이

소스코드 : C++

1. 유클리드 호제법에 의한 GCD 함수 구현
2. GCD 함수와 $ a \times b \div G$ 를 이용하여 LCM 함수 구현
3. answer에 가장 첫번째 수를 넣어둔다.
4. 다음 수를 하나씩 꺼내어 두 수의 최소공배수를 구한 후 answer에 넣어준다.
5. 이 과정을 반복한다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int GCD(int a, int b){
    if(a%b==0)return b;
    return GCD(b, a%b);
}
int LCM(int a, int b){return (a*b)/GCD(a,b);}
int solution(vector<int> arr) {
    int answer = arr[0];   
    for(int i=1; i<arr.size(); i++)
        answer = LCM(answer,arr[i]);

    return answer;
}

소스코드 : Python

파이썬으로 풀때에는 재귀함수를 지양하려고 노력중이다. 찾아보던 중 lambda 함수를 알게 되었는데, lambda 함수는 파이썬에서 제공하는 익명함수이다.

lambda 매개변수 : 반환 값으로 정의된다.

def solution(arr):
    answer = arr[0]
    GCD = lambda a, b : b if a%b==0 else GCD(b,a%b)
    LCM = lambda a, b : int(a*b/GCD(a,b))
    for i in range(1,len(arr)):
        answer = LCM(answer,arr[i])
    return answer