[Lv. 2] N개의 최소공배수

안녕하세요. 

강렬한 스포트라이트 입니다!

 

하기의 문제를 Python 언어를 사용하여 구현하고자 합니다.

 

<문제 설명>

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

 

<제한 사항>

arr은 길이 1이상, 15이하인 배열입니다.
arr의 원소는 100 이하인 자연수입니다.

 

<입출력 예>

arr	return
[2,6,8,14]	168
[1,2,3]	6

 

<해결 코드>

 

1) 우선 두 수의 최소공배수를 반환하는 함수 lcm을 구현합니다.

이후 스택 자료 구조를 사용하여 리스트가 비어있으면 값을 쌓아 올려주고, 비어있지 않으면 마지막에 삽입된 값과 검색하는 값에 대해 함수 lcm을 호출하고, 리턴된 값을 리스트에 삽입합니다.

끝으로 arr 리스트 내의 모든 값에 대한 확인되면 stk 리스트 내의 마지막 값을 리턴합니다. 

 

def lcm(a, b):
    for i in range(max(a,b),(a*b)+1):
        if i%a==0 and i%b==0:
            return i
def solution(arr):
    stk = []
    for a in arr:
        if not stk:
            stk.append(a)
        else:
            stk.append(lcm(stk.pop(), a))
    return stk[-1]

 

 

2) arr 리스트 내의 첫번째 값을 answer 변수에 초기화해주고,

arr 리스트 내의 값에 대해서 gcd 함수를 사용하여 최소공배수를 구해준 후, answer의 값을 업데이트 해줍니다.

끝으로 answer의 값을 반환합니다.

import math
def solution(arr):      
    answer = arr[0]
    for a in arr:
        answer = a * answer // math.gcd(a, answer)
    return answer

 

 

해보시고 문의사항이 있으시면 댓글로 남겨주세요.´◡`

감사합니다!