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;
}
'코딩테스트 > Programmers' 카테고리의 다른 글
| [코딩테스트/Programmers] 16_직사각형 별찍기 (Lv1.) (0) | 2022.01.10 |
|---|---|
| [코딩테스트/Programmers] 15_같은 숫자는 싫어 (Lv1.) (0) | 2022.01.10 |
| [코딩테스트/Programmers] 13_문자열 다루기 기본 (Lv1.) (0) | 2022.01.04 |
| [코딩테스트/Programmers] 12_문자열 내림차순으로 배치하기 (Lv1.) (0) | 2022.01.03 |
| [코딩테스트/Programmers] 11_문자열 내 p와 y의 개수 (Lv1.) (0) | 2022.01.03 |
