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

0. 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12953

프로그래머스

 

1. 문제 설명

1) 주어진 리스트에서 최소공배수 구하기

 

2. 입출력

# input
arr = [2, 6, 8, 14]

# output
result = 168

 

3. 코드

import math
def solution(arr):
    arr.sort()                                              # 배열 정렬
    answer = arr[0]                                         # 가장 작은 수로 시작

    for i in arr:
        # 2개의 최소공배수를 구하고 answer에 저장 후 다시 최소공배수 구하기
        answer = (i * answer) // math.gcd(i, answer)
    return answer

 

실행 결과

 

4. 회고

이 문제는 배열을 정렬한 뒤, 두 수의 곱을 두 수의 최대공약수로 나누어서 최소공배수를 구하는 원리를 적용해서 해결하는 것이 핵심이다. 처음 문제를 해결할 때에는 우리가 일반적으로 최소공배수를 구하는 것처럼 공약수를 이용해서 문제를 해결하고자 했는데, arr = [2, 7, 14]와 같이 주어지는 경우 세 수의 공약수가 아니라 두 수의 공약수를 고려해야 하기 때문에 연산이 복잡해진다. 따라서 수학적 성질을 이용하여 문제를 푸는 것이 이 문제에서 중요한 해결 방법이 되었다.

 

5. Github

https://github.com/iihye/Algorithm/blob/main/Programmers/n_lcm.py

GitHub - iihye/Algorithm