lv2 N개의 최소 공배수

문제 링크

• N개의 최소공배수

문제 설명

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

 

제한사항

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

 

입출력 예

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

 

풀이

• 최대공약수는 math 라이브러리에서 gcd함수를 사용하면 됨
• 최소공배수는 두값을 곱하고 최대 공약수로 나누었을 때의 값임. 주의! math 라이브러이에서 gcd는 정수값만 읽음 하지만 나눗셈을 하면 float이 되므로 int값으로 바꿔줘야함
• 3개의 수에 대한 최대공약수는 두개에 대한 최대공약수와 나머지 수 사이에 다시 최대공약수를 구하면 됨
• 3개의 수에 대한 최소공배수는 두개에 대한 최소공배수와 나머지 수 사이에 다시 최소공배수를 구하면 됨

 

코드

sol1)  최대 공약수를 함수로 만들어서 푸는 풀이

# N개의 최소공배수

def gcd(x,y):
    while x!= 0:
        y , x = x , y%x   # 주의!     y = x
                          #           x = y%x  이렇게 두줄로 쓰면 오답이 나옴. 그 이유는 위에서 할당된 y가 밑에서 적용되기 때문에
    return y    

def lcm(x,y):
    return int(x*y/gcd(x,y))

def solution(arr):
    m = arr.pop()
    n = arr.pop()
    
    l_c_m = lcm(m,n)
    while arr:
        l_c_m = lcm(l_c_m, arr.pop())
    return l_c_m

 

sol2)  math함수를 이용한 풀이

from math import gcd


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

    return answer

 

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges