URL https://programmers.co.kr/learn/courses/30/lessons/12953
문제 설명
- 두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.
제한 사항
- arr은 길이 1이상, 15이하인 배열입니다.
- arr의 원소는 100 이하인 자연수입니다.
문제 풀이
- 최대 공약수 (gcd) : 두 수의 공통된 약수 중 공통이 되는 가장 큰 숫자
- 최소 공배수 (lcm) : 두 수의 배수 중 공통이 되는 가장 작은 숫자로
두 수의 곱을 최대 공약수로 나눈 값과 같음 - arr의 2수의 최대 공약수를 활용하여 최소 공배수를 구함
- 위의 방법을 arr의 배열에 1개가 남을때까지 하면 해당 숫자가 최소 공배수임
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import math
# 최소 공약수를 활용한 최대 공배수
def lcm(a, b):
l = int(math.gcd(a, b))
return int(a * b / l)
def solution(arr):
while len(arr) != 1:
a = arr.pop()
b = arr.pop()
c = lcm(a,b)
arr.append(c)
return arr[0]
1
2
arr = [2,6,8,14]
solution(arr)
1
168
1
2
arr = [1,2,3]
solution(arr)
1
6