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

프로그래머스 12953번 문제인 "N개의 최소공배수" Lv.2을 파이썬으로 풀어보도록 하겠습니다.

[프로그래머스] N개의 최소공배수 Lv.2 - [파이썬/python]

 

 

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

---

💻 문제 설명

 

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다.

 

예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다.

 

n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환(return)하는 함수, solution을 완성해 주세요.

 

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

프로그래머스

---

🚨 제한사항

 

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

---

 

 

---

---

---

!!!정답 주의!!!

---

---

---

 

 

 

---

🌟 소스 코드

 

프로그래머스-N개의-최소공배수-파이썬-코드

 

 

 

def solution(arr):

   

    result = 1

   

    # arr에 대해 순회하면서 최소공배수 업데이트

    for i in arr:

        result = lcm(result, i)

       

    return result

# 최대공약수 구하는 함수

def gcd(x, y):

   

    while y:

        x, y = y, x%y

       

    return x

# 최소공배수 구하는 함수

def lcm(x, y):

   

    return x * y // gcd(x, y)

 

 

 

---

⏱ 시간복잡도

 

위 코드의 시간복잡도는 O(n log m)입니다.

 

 

반복문 순회하기: for i in arr:

모든 원소를 순회하는 데는 O(n)의 시간이 소요됩니다. 여기서 n은 배열의 길이입니다.

 

최대공약수 구하기: gcd(x, y)

유클리드 호제법을 사용하여 최대공약수를 구합니다. 이 알고리즘의 시간 복잡도는 O(log min(x, y))입니다. 여기서 x와 y는 두 수입니다.

 

최소공배수 구하기: lcm(x, y)

최대공약수를 이용하여 최소공배수를 구합니다. 이 연산은 상수 시간, 즉 O(1)의 시간 복잡도를 가집니다.

 

따라서, 이 코드는 배열을 한 번만 순회하고, 각 원소에 대해 로그 시간의 연산을 수행하므로, 전체 시간 복잡도는 O(n log m)입니다. 여기서 m은 배열의 원소 중 최댓값입니다. 이는 입력 크기에 대해 로그 선형적으로 비례하는 시간 복잡도를 의미합니다.

---

🏳‍🌈 테스트 결과

 

프로그래머스-N개의-최소공배수-상태

 

프로그래머스-N개의-최소공배수-테스트-결과