프로그래머스 Lv2 N개의 최소공배수 (python)

N개의 최소공배수

풀이

최소공배수를 구해야 하는 문제이다.
다만 2개의 수에서 최소공배수를 구하는 것이 아닌 N개의 수에서 최소공배수를 구해야 한다.

N개라고 별반 다르지 않으니 최소공배수 공식을 그대로 이용해 주었다.
1. 유클리드 호제법을 이용해 최대공약수 함수와 최소공배수 함수를 만들어준다.
2. 입력받은 리스트의 길이가 1보다 크다면 arr [0]와 arr [1]의 최소공배수를 구해서 arr [0]에 입력하고 arr [1]은 제외시킨다.
3. 2를 반복하고, 그 결과 arr의 길이가 1이 된다면, arr [0]의 값을 return 한다.

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
def lcm(a, b):
    return a * b // gcd(a, b)
def solution(arr):
    if len(arr) == 1:
        return arr[0]
    while len(arr) > 1:
        arr[0] = lcm(arr[0], arr[1])
        arr.pop(1)
    return arr[0]

다른 사람 풀이

최대공약수를 import 해서 푼 방법이 있었다. 이런 게 있는 줄은 몰랐다.
내가 한 방식과 크게 다르진 않았다.
이 방법은 미리 answer에 입력시키고, for문을 이용해서 최소공배수를 구하고 answer에 최소공배수를 입력시켰다.

from fractions import gcd


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

    return answer

print(nlcm([2,6,8,14]));

그리고 상남자의 풀이가 있어서 한 번 가져와봤다.
멋지군.

import math
def solution(arr):
    answer = 1
    stack=[]
    tmp=[0]*100
    count=[0]*100
    arr_acc=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
    for i in arr:
        stack=[]
        while i>1:
            if i%2==0:
                i=i//2
                stack.append(2)
            elif i%3==0:
                i=i//3
                stack.append(3)
            elif i%5==0:
                i=i//5
                stack.append(5)
            elif i%7==0:
                i=i//7
                stack.append(7)
            elif i%11==0:
                i=i//11
                stack.append(11)
            elif i%13==0:
                i=i//13
                stack.append(13)
            elif i%17==0:
                i=i//17
                stack.append(17)
            elif i%19==0:
                i=i//19
                stack.append(19)
            elif i%23==0:
                i=i//23
                stack.append(23)
            elif i%29==0:
                i=i//29
                stack.append(29)
            elif i%31==0:
                i=i//31
                stack.append(31)
            elif i%37==0:
                i=i//37
                stack.append(37)
            elif i%41==0:
                i=i//41
                stack.append(41)
            elif i%43==0:
                i=i//43
                stack.append(43)
            elif i%47==0:
                i=i//47
                stack.append(47)
            elif i%53==0:
                i=i//53
                stack.append(53)
            elif i%59==0:
                i=i//59
                stack.append(59)
            elif i%61==0:
                i=i//61
                stack.append(61)
            elif i%67==0:
                i=i//67
                stack.append(67)
            elif i%71==0:
                i=i//71
                stack.append(71)
            elif i%73==0:
                i=i//73
                stack.append(73)
            elif i%79==0:
                i=i//79
                stack.append(79)
            elif i%83==0:
                i=i//83
                stack.append(83)
            elif i%89==0:
                i=i//89
                stack.append(89)
            elif i%97==0:
                i=i//97
                stack.append(97)

        uni=list(set(stack))
        for i in uni:
            m=stack.count(i)
            k=max(count[i],m)
            count[i]=k

    for l in range(len(count)):
        if count[l]!=0:
            answer=answer*(l**count[l])

    return answer