[Programmers / Level2] N개의 최소공배수

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

프로그래머스

---

 

<내코드 - 오답>

def solution(arr):
    total, common_val = 1, 1
    for i in range(2, min(arr) + 1):
        for value in arr:
            if value % i != 0: break
            common_val *= i
            break
    for value in arr:
        total *= value // common_val
    return total * common_val

 

-> 오랫만에 만나는 최대공약수, 최소공배수 문제이다. 단순무식하게 arr에 존재하는 가장 작은 수를 기준으로하여 최대공약수를 구하려고 시도했다. 사실 공약수, 공배수 문제는 접근방법이 정해져있는 문제이다.

 

 

 

<정해코드>

출처: https://bit.ly/4aTz91f

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

def solution(arr):
    answer = arr[0]
    for num in arr[1:]:
        answer = lcm(answer, num)
    return answer

-> 유클리드 호제법을 사용하여 GCD(최대공약수)를 구할 수 있다.

gcd를 구했으면 배열에 존재하는 모든 원소들을 조사하면서 LCM(최소공배수)를 찾아간다면 가장 효율적이게 원소를 찾을 수 있다.

놀라운 사실은 파이썬에서 math 라이브러리에서 gcd 메소드가 존재한다는 점이다. 역시 갓이썬..