[프로그래머스 Lv2, python]- N개의 최소공배수

def solution(arr):
    an=1
    li=[[1] for a in range(len(arr))] #소인수 분해를 저장할 리스트. 1은 모든수에 들어가서 미리 저장
    idx=0 # 리스트의 인덱스
    for a in arr:
        b=2 #2부터 나눠주기
        while(b<=a):
            if a%b==0: 
                a//=b
                li[idx].append(b)
                b=2 #최소의 숫자로 나눠주기위해 초기화해주는
            else:
                b+=1      
        idx+=1
    stack=[] # 각 소인수분해들 중에서 같은 숫자중 많은 수를 가진거 저장하기
    for i in li:
        for j in i:
            if j not in stack: # 없는 수이면 추가해주기
                stack.append(j)
            else:
                if stack.count(j)<i.count(j): # 스택에있는 숫자의 수보다 리스트안에 있는 숫자의 수가 클때 추가
                    stack.append(j)
    for i in stack: #곱해주기
        an*=i
    return an

처음에 최대공약수랑 최소공배수 구하는거 잘몰라서 복잡하게 풀었다..

def lcm(a,b): #최소 공배수. 
    return a*b//gcd(a,b)

def gcd(a,b): #최대 공약수.유클리드 호제법 사용
    if a%b==0:
        return b
    return gcd(b,a%b)

def solution(arr):
    answer=arr[0]
    for num in arr[1:]:
        answer=lcm(answer,num)
    return answer

최소공배수는 lcm으로, 두 수를 곱한뒤 최대공약수를 나누어줘야함.

 

최대공약수는 유클리드 호제법을 사용함.

만약 48과 18을 구할때, 48%18=12이고, 다시 뒤에 두 숫자의 나머지를 구해서 0이될때까지 하는것임. 18%12=6, 12%6=0이므로 최대공약수는 6이된다. 

이를 a,b로 한다면 위의 함수와 같이 사용할 수 있다.

 

또한 두개씩 비교해야한다.