프로그래머스 - 최대공약수 최소공배수

문제 설명

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

제한 사항

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

입출력 예

nmreturn

3	12	[3, 12]
2	5	[1, 10]

입출력 예 설명

입출력 예 #1
위의 설명과 같습니다.

입출력 예 #2
자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

 

나의 풀이

def solution(n, m):
    answer = []
    n_measure = [i for i in range(1, n+1) if n % i == 0]
    m_measure = [j for j in range(1, m+1) if m % j == 0]
    
    for k in m_measure[::-1]:
        if k in n_measure:
            min_measure = k
            answer.append(k)
            break
    
    max_measure = k * (n/k) * (m/k)
    answer.append(max_measure)
    
    return answer

1) n, m의 모든 약수를 구한다.

 

2) 둘 중 한개의 약수의 리스트를 중심으로 for문을 돌려 (큰값부터) 다른 리스트의 값이 있는지 확인! 있으면 for문을 나오고 가장 먼저 나온 수가 최대 공약수

 

3) 최대공약수를 통해 최소공배수를 구한다!

 

개선 풀이

def gcd(a, b):     #유클리드 호제법! 최대공약수를 구하는 식!
    while b > 0:
        a, b = b, a % b
    return a
    
def solution(n, m):     #유클리드 호제법을 활용한 최소공배수 구하기!
	answer = []
    min_measure = gcd(n, m)
    max_measure = n * m / min_messure    
    
    answer = [min_measure, max_measure]
    
    return answer

유클리드 호제법

유클리드 호제법이란, 숫자 a, b가 있을 때, a를 b로 나눈 나머지와 b 의최대 공약수 는 a 와 b 의 최대 공약수 가 같다는 것을 의미한다.

그럼, 계속해서 a 를 b로 나누어서 b를 a에 나눈 나머지를 b 에 대입시켜서 b 가 0이 될때 까지 반복을 하면, 남는 a 값이 바로 최대 공약수 이다.

 

두 풀이 비교

첫 풀이는 구하지 않아도 되는 모든 약수를 구하기에 비효율적이다. 유클리드 호제법을 사용하여 최대공약수만 구해주는 식을 완성할 수 있다. 실제로 시간 복잡도가 많이 줄어들었다. 아마 첫 풀이는 O(2n)정도 될 것이라 생각이 들고, 유클리드 호제법 풀이는 O(n)보다 작을 것이라 예상이 된다! 거의 0.0x 시간이 나왔었다! 최대공약수 문제가 나오면 유클리드호제법을 기억하자!