프로그래머스 | 최대공약수와 최소공배수 (Python3)

 

오늘도 오랑이는 문제를 풉니다.

 

최대공약수와 최소공배수

 

최대공약수, 최소공배수의 특징을 알고 활용하는 문제입니다.

1. 최대공약수 = 두 수 중 큰 수를 작은 수로 나눴을 때의 나머지 값 m%n

2. 최소공배수 = 두 수의 곱을 최대공약수로 나눈 값 (m*n) / (m%n)

 

그래서 아래와 같이 풀었는데 어김없이 틀렸습니다. 

입력이 9, 7 일 때의 케이스에 대한 나머지 계산이 더 필요하기 때문입니다. 

def solution(n, m):
    b, a = max(n,m), a = min(n,m)
    if b%a == 0:
        answer = [a,b]
    else:
        answer = [b%a,(b*a)/(b%a)]        
    return answer

 

가장 간단한 풀이는 아래와 같이 작은 수 n 에 대해 하나씩 돌아가면서 GCM 이 되는지 대조해보는 방법입니다. 

하지만 n ,m 이 크면 돌아가는 데 오래 걸려 비효율적인 코드가 됩니다. 

def solution(n, m):
    a = min(n,m)
    for i in range(1,a+1):
        if n%i==0 and m%i==0:
            answer = i  
    return [answer, n*m//answer]

 

아래 풀이는 유클리드 호제법 Euclidean Algorithm 의 원리를 활용한 수학적으로 정석인 풀이법이며, 실제로 코드를 제출했을 때 런타임이 가장 짧은 효율적인 코드입니다. 

 

Euclidean Algorithm

☞ 두 수의 최대공약수(GCD)는 두 수를 나눴을 때 m/n 나머지가 0이 될 때의 n 값  

 

The Euclidean algorithm is based on the principle that the GCD of two numbers does not change if the larger number is replaced by its difference with the smaller number. 

 

즉,  a, b = min(a, b), max(a,b) 일 때 a, b = b, a % b 

 

☞  두 수의 최소공배수(LCM)는 두 수의 곱을 GCD로 나눈 값입니다. (m*n) / (m%n)

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, n*m//a]
    return answer

 

input이 [9, 7]일 때 while문은 아래와 같은 패턴을 출력하며 마지막에 LCD, GCM을 출력합니다. 

9 7

7 2

2 1

1 0

 

오랑우탄이 영어를 하고 오랑이가 코딩마스터가 되는 그날까지~

 

 

프로그래머스