[프로그래머스] 연습문제 > N개의 최소공배수

programmers.co.kr/learn/courses/30/lessons/12953?language=python3

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

 

문제 설명

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

제한 사항

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

입출력 예

arrresult

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

 

 

---

풀이

굉장히 단순하게 생각하였다.
여러 숫자들 중의 최소공배수는 가장 큰 값의 배수이라는 논리로 구현했다.

오름차순 정렬 후 pop()을 해 가장 큰 값을 max에 저장해둔다.
무한루프 돌려서 가장 큰 값의 배수를 다른 숫자로 나누어 떨어지면
count를 +1이해준다 카운트 값이 배열 길이와 같으면 모두 나누어 떨어지는
즉, 최소공배수이다.

def solution(arr):
    arr.sort()
    max = arr.pop()
    multiple_num = 1
    while True:
        count = 0
        temp = max * multiple_num 
        for i in arr:
            if temp % i ==0:
                count += 1
        if count == len(arr):
            return temp
        multiple_num += 1    

 

다른사람의 풀이 ==> 내장 함수인 gcd함수 사용
최소공배수 = 두 수의 곱 // 최소 공약수

from fractions import gcd


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

    return answer