[프로그래머스] Level 2_N개의 최소공배수(연습문제)

📌문제 유형

연습문제

 

📌문제

프로그래머스

 

📌나의 문제풀이

1차 시도

 - AttributeError: module 'math' has no attribute 'lcm'

python3.9 버전이 아니므로 작동 안됨

import math

def solution(arr):
    return math.lcm(arr)

2차 시도

import math

def solution(arr):
    answer, gcd_num = 1, 0
    gcds = []
    
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            gcds.append(math.gcd(arr[i], arr[j]))
    gcd_num = min(gcds)
    
    for num in arr:
        answer *= num//gcd_num
    answer *= gcd_num
    
    return answer

3차 시도(다른 사람 풀이)

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

def solution(arr):
    from math import gcd                            # 최대공약수를 구하는 gcd() import
    answer = arr[0]                                 # answer을 arr[0]으로 초기화

    for num in arr:                                 # 반복문을 처음부터 끝까지 돈다.
        #1. (arr[0],arr[1])의 최소공배수를 구한 후 answer에 저장
        #2. (#1에서 구한 최소공배수, arr[2])의 최소공배수를 구한 후 answer에 저장
        #3. 모든 배열을 돌면서 최소공배수를 구하고, 저장하고 하는 방식을 진행
        answer = answer*num // gcd(answer, num)     

    return answer

 

📌다른사람의 문제풀이

 1) gcd 작동을 직접 만든 후 동일한 풀이

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)


def nlcm(num):
    num.sort()
    max_num = num[-1]
    # print (num, max_num)
    temp = 1
    for i in range(len(num)):
        # lcm = (a*b) / gcd
        # gcd = (a*b) / lcm
        temp = (num[i] * temp) / (gcd(num[i], temp))
        # print (temp)
    return temp

2) reduce 사용

 - reduce : 여러개를 대상으로 누적집계 가능

파이썬 reduce 함수 사용법

from functools import reduce
from fractions import gcd

def nlcm(num):
    return reduce(lambda a, b : a * b // gcd(a, b), num)

3) 유클리드 호제법 사용

[유클리드 호제법]

두 수 a, b가 있을 때 (a > b)
a % b == 0이면 b가 GCD입니다.
a % b != 0이면 (c = a % b라고 할 때)
b % c를 구해서 0이 나올때까지 반복합니다.

출처 : https://school.programmers.co.kr/questions/26061

# 2개 수의 최소공배수 구하는 함수
def least(a, b):
    A, B = a, b
    while b > 0:
        a, b = b, a % b
        
    GCD = a # 최대공약수
    return A * B // greatest

# arr에서 앞 2개씩 접근하면서 최소공배수 갱신
def solution(arr):
    arr.sort()
    temp = arr[0]
    for i in range(0, len(arr)-1):
        temp = least(temp, arr[i+1])
    return temp

 

📌리뷰

 - 최소공배수 = (a*b) // (두 수의 최소공배수)