N개의 최소 공배수

먼저 이 문제를 보자마자 풀었을 때는 유클리드 호제법과 같은 방식이 떠오르지 않아서 무식한 방법으로 풀었다.

def solution(arr):
    arr.sort()
    for i in range(arr[len(arr) - 1], 10 ** 16):
        minimum = True
        for j in arr:
            if i % j != 0:
                minimum = False
                break

        if minimum:
            return i

최소 공배수이기 때문에 주어진 배열 중 가장 큰 값이 일단 최소공배수중 최소인 경우가 될 것이기 때문에 그냥 배열의 마지막 인덱스를 시작으로 숫자를 1씩 늘려가며 배열의 인덱스의 숫자들과 모두 나누어 떨어지는지를 반복했다. 결과적으로 통과하긴 했는데... 풀어놓고도 찜찜해서 다시 찾아서 풀어보았다.

유클리드 호제법

먼저 유클리드 호제법을 이용해 최대 공약수를 구했다.

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

주어진 두 수 (a,b)를 b가 0이 될 때 까지 a%b를 한 것을 tmp에 넣어주고 a에 b를 b에 tmp를 넣어주면 그 결과(a)가 최대 공약수가 된다.

최소공배수

그 후 최소 공배수를 구해주는데 학창시절 배웠듯이 주어진 두 수(a,b)가 있으면 a*b = 최대공약수*최소공배수이다.
즉 최소공배수 = a*b/최대공약수라는 뜻이다.

이것을 이용해서 코드를 작성해보면

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


def solution(arr):
    lcm = arr[0]
    for i in arr:
        lcm = lcm * i / gcd(lcm, i)
    return int(lcm)

가 된다. 프로그래머스는 레벨1은 그냥 풀고 레벨2부터는 블로그의 기록을 남겨야겠다는 생각이 이 문제를 보자마자 들었다. 잊지 말고 꾸준히 복습을 해야겠다.