Programmers / N개의 최소공배수 / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: N개의 최소공배수 (2단계)

문제 사이트: https://programmers.co.kr/learn/courses/30/lessons/12953

---

나의 풀이

def solution(arr):
    max_num = max(arr) # 리스트에서 가장 큰수
    n = 1
    while True:
        
        answer = max_num * n # 가장 큰수의 배수를 최소공배수로 
        tmp = True
        for i in arr:
            tmp = True
            
            if max_num * n % i != 0: # 리스트 안의 수가 최소공배수의 배수의 약수가 아닐경우
                tmp = False # False를 반환
                break # for 문을 빠져나가고 n+1을 해줌
        if tmp == True: # for 문의 조건
            break #while 문을 빠져나감
        
        n += 1 
    return answer

최대공약수와 최소공배수

 

이미지[1]

+) GCD 함수를 이용한 풀이

gcd( greatest common divisor)- 최대공약수 

math.gcd 함수는 최대공약수를 구하는 함수이다. 

1. 라이브러리 없이  gcd 함수 나타내기

def gcd(a, b): # 두 수의 최대공약수를 구하는 함수
    if a % b == 0: # 만약 a를 b로 나눈 나머지가 0이면
        return b # b가 최대 공약수다
    else: # a를 b로 나눈 나머지가 0이 아니라면
        return gcd(b,a%b) # a, b = b, a%b 로 재귀함수 호출

# 람다식으로 표현한 경우
gcd = lambda a, b: a if not b else gcd(b, a%b)

 

풀이

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

def solution(arr):
    for i in range(1, len(arr)):
        arr[i] = arr[i-1] * arr[i] // gcd(arr[i-1], arr[i])
    return arr[-1]

2. 라이브러리를 이용하여 gcd함수 나타내기

 

from math import gcd

def solution(arr):
    for i in range(1, len(arr)):
        arr[i] = arr[i-1] * arr[i] // gcd(arr[i-1], arr[i])
    return arr[-1]

 

 

reference

 

- gcd함수 https://wikidocs.net/106252

- 이미지[1] https://jwj4519.com/entry/%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98%EC%99%80-%EA%B3%B5%EB%B0%B0%EC%88%98-%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98-%EA%B5%AC%ED%95%98%EB%8A%94-%EB%B0%A9%EB%B2%95

---