풀이_N개의최소공배수.md

🐡 프로그래머스 N개의 최소공배수

• Date : 2021.02.14(일)
• Time : 30분

문제

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

• 제한사항

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

코드 풀이

    while len(arr) > 1 :
        a, b = arr.pop(0), arr.pop(0)
        arr.append(a*b // gcd(a,b))
        arr.sort()

: 여러개의 최소공배수를 구하려면 앞에서부터 2개의 수를 최소공배수로 만들어주는 과정을 통해 구현할 수 있다. 예시로 [2,6,8,14] -> [6,8,14] -> [24,14] -> [168] 가 될 수 있다. 그리고 두개 수의 최소공배수는 두 수의 곱셈 / 두 수의 최대공약수 로 구할 수 있다. 최대공약수는 from fractions import gcd 모듈을 사용할 수 도 있지만, 속도의 측면에서 직접 구현해보았다.

def gcd(a, b): # 최대공약수 구하기
    if a % b == 0: return b
    else: return gcd(b, (a % b))

: 유클리드 호제법을 이용한 알고리즘이다. 만약 a와 b가 바로 나눠떨어진다면 작은 수가 큰 수의 최소공배수인 것 이다. 하지만 바로 나눠떨어지지 않는다면 a,b의 최소공배수 = b, a%b의 최소공배수 인것을 이용해 풀어주었다.

ex. 12, 8의 최소공배수 = 8,4의 최소공배수