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

문제

프로그래머스 연습문제

• Lv 2. N개의 최소공배수 (Python)
  https://school.programmers.co.kr/learn/courses/30/lessons/12953

코드 구현

def solution(arr):
    answer = 0

    num1 = arr[0]   # 초기 num1은 배열의 첫번째 값
    for i in range(1, len(arr)):
        num2 = arr[i]
        # num1과 num2의 최소공배수를 구하는 부분
        for n in range(max(num1, num2), num1 * num2 + 1):
            if (n % num1 == 0 and n % num2 == 0):
                num1 = n    # 현재 num1과 num2의 최소공배수를 다음 num2와 비교해서 또 그 둘의 최소공배수를 계속 구해야하기 때문에 num1 업데이트
                break

    answer = num1   # 마지막으로 구해진 최소공배수가 배열에 있는 모든 N개의 값에 대한 최소공배수

    return answer

풀이

• 여러개의 최소공배수를 구하는 방법
  • ex) a, b, c의 최소공배수 1) a와 b의 최소공배수를 구한다. 2) 1번에서의 값과 c의 최소공배수를 구한다. 3) 2번에서 나온 값이 a b c 모두의 최소공배수가 된다.
    
• 파이썬에서 최소공배수 for문으로 구하는 방법
  • 최소 num1이나 num2 이상이여야 하기 때문에 둘 중 큰 값부터 시작해야한다.
  • 따라서 max(num1, num2)부터 num1 * num2까지 따져가면서 둘 다 나누어 떨어지는 수가 나온다면 → 그 둘의 최소공배수이다.

What I learned

최대공약수 gcd()를 이용해서 해결하는 정답 코드

• num1과 num2의 최소공배수 = (num1 * num2) / num1과 num2의 최대공약수

from fractions import gcd

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

    return answer