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

https://school.programmers.co.kr/learn/courses/30/lessons/12953

프로그래머스

 

사전 지식 

python에서 최대공약수, 최소공배수 구하는 방법 

- a,b의 최대공약수 : math.gcd(a,b)

- a,b의 최소공배수 : a*b/math.gcd(a,b)

 

코드

내 코드(정답)

from math import gcd

def solution(arr):
    stack = []
    for i in arr:
        if not stack:
            stack.append(i)
        else:
            a = stack.pop()
            stack.append(int(a*i/gcd(a, i)))
    return stack[0]

다른 사람 코드 보니 굳이 stack 에 넣을 필요가 없긴 했구나

 

다른 코드

from math import gcd

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

    return answer

 

비고)

처음 접근했던 방법

각 요소의 최대공약수를 다 곱해서 요소들의 곱에서 나눠주면 되지 않을까 생각하긴했음

from math import gcd
from functools import reduce

def solution(arr):
    answer = reduce(lambda x, y: x * y, arr)
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            print(arr[i], arr[j], ": gcd = ", gcd(arr[i], arr[j]))
            answer /= gcd(arr[i], arr[j])
    return answer

# 이렇게 해주고 stack에 있는 요소 중 똑같거나, stack 요소의 곱으로 해당 숫자를 만들어 낼 수 있으면 append하지 않으면 될 거 같은데 ..

근데 최대공약수 중에서 중복되는 요소들이 있으면 그거 빼고 해줘야 하는걸 알았음

너무 복잡해질 뿐더러 시간도 오래걸릴 것 같아서(시간복잡도) 다른 접근을 시도함

그게 위 정답 코드