[코딩테스트/Programmers] 14_N개의 최소공배수 (Lv2.)

N개의 최소공배수

 

 문제 설명

 

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

 

 제한 사항

 

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

 

 입출력 예

 

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

 

 Python 코드

 

import math

def solution(num):
    answer = num[0]
    for n in num:
        answer = (n * answer) // math.gcd(n, answer)
    return answer

• 최대공약수 gcd는 math.gcd를 이용해 구해주고,
   
  최소공배수 lcm은 A * B // gcd(A,B) 이므로 for문을 돌면서 맨 마지막 answer를 return 해주면 된다.

* 참고 링크 : https://wookcode.tistory.com/101

def solution(arr):
    answer = 0
    max_num = 1
    for a in arr:
        max_num *= a
    
    for i in range(2, max_num+1):
        for a in arr:
            if i%a != 0:     # 나누어 떨어지지 않는다면 break
                break
                             # 위에서 break에 걸리지 않았다면 
                             # 모두 나누어 떨어지는 것이기 때문에 해당 i를 answer에 대입
        else:
            answer = i
            break
    return answer

* 참고 링크 : https://kimmeh1.tistory.com/190

 C++ 코드

 

#include <string>
#include <vector>

using namespace std;
int GCD(int a, int b){         // 최대공약수
    if(a == 0) return b;
    return GCD(b % a, a);
}
int LCM(int a, int b){         // 최소공배수
    return a * b / GCD(a,b);
}
int solution(vector<int> arr) {
    int answer = 0;
    answer = arr[0];
    for(int i=1;i<arr.size();i++){
        answer = LCM(answer, arr[i]);
    }
    return answer;
}

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

using namespace std;

int gcd(int x, int y) { return x % y == 0 ? y : gcd(y, x % y); }
int lcm(int x, int y) { return x * y / gcd(x, y); }
int solution(vector<int> arr) {
    int answer = arr[0];
    for (int i = 1; i < arr.size(); i++)
        answer = lcm(answer, arr[i]);
    return answer;
}