[프로그래머스] Lv1. 최대공약수와 최소공배수

문제

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

제한 조건

• 두 수는 1이상 1000000이하의 자연수입니다.

나의 풀이:

def solution(n, m):
    a = [i for i in range(1,n+1) if n%i==0]
    b = [i for i in range(1,m+1) if m%i==0]
    comm_div = [j for j in b for i in a if i == j]
    
    c = [i for i in range(n, n*m+1) if i%n==0]
    d = [i for i in range(m, n*m+1) if i%m==0]
    comm_mul = [j for j in d for i in c if i == j]
    
    return [max(comm_div), min(comm_mul)]

문제를 풀기 위해 먼저 최대공약수와 최소공배수를 정의했다.

• 최대공약수는 n과 m 각각의 약수 중에서 공통된 약수의 최댓값
• 최소공배수는 n과 m 각각의 배수 중에서 공통된 배수의 최소값, 이 때 최소공배수는 n과 m을 곱한 값보다 클 수 없다.

이런 특성을 기준으로 위 코드를 우선 생각나는 대로 작성했다. 그리고 작성된 코드에 공통되는 부분이 많이 보여서 이를 하나로 통일시켜 봤다.

def solution(n, m):
    if n > m: n, m = m, n
    comm_div = [i for i in range(1,n+1) if n%i==0 and m%i==0]
    comm_mul = [i for i in range(m, n*m+1) if i%n==0 and i%m==0]
    return [max(comm_div), min(comm_mul)]

최대공약수의 경우 n 또는 m보다 더 클 수 없기 때문에 range 최대값을 더 작은 수로 지정해주고, 최소공배수의 경우 n 또는 m 보다 더 작을 수 없기 때문에 range 최소값을 더 큰 수로 지정해주었다.

다른 사람들의 풀이:

def solution(n, m):
    a, b = max(n, m), min(n, m)
    t = 1
    while t > 0:
        t = a % b
        a, b = b, t
    answer = [a, int(n*m/a)]
    return answer

“유클리드 호제법”을 사용한 풀이라고 한다.

상당히 어렵게 느껴졌는데 아직 레벨 1이라니… 최대공약수와 최소공배수의 원리에 대한 이해가 부족하다보니 더 어려웠던 것 같다. 유클리드 호제법은 나중에 다시 한번 공부를 해봐야할 것 같다…