최대공약수와 최소공배수 / 프로그래머스, 파이썬 코딩테스트 연습연습문제

문제

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

 

 

제출답안

def solution(n, m):
    def list_divisor(number):
        """
        정수를 받아 공약수의 리스트를 리턴하는 함수
        @ param number : Int
        
        """
        ls_cd = [num for num in range(1, number+1) if number%num ==0 ]
        return ls_cd
    
    # 각 수의 공약수 집합
    set_n, set_m = set(list_divisor(n)), set(list_divisor(m))
    
    # 두 집합의 교집합의 최대
    gcd = max(set_n.intersection(set_m))
    
    # 최소공배수
    lcm = abs(n*m) / gcd
    
    answer = [gcd, lcm]
    return answer

 

출처: 최소공배수 - 위키백과

 

제출 후 개선답안

다른 사람의 풀이를 통해 유클리드 호제법을 알게됨
위키백과의 유클리드 호제법을 적용하여 코드를 간결화하였음

def solution(n, m):
    
    # 큰 수와 작은 수
    big, small = max(n, m), min(n, m)
    
    # 유클리디언 호기법을 코드로 옮겨봄
    while(small !=0):
        big , small = small, big%small
    
    # 최소공배수
    lcm = abs(n*m)/big
           
    answer=[big, lcm]
    return answer

 

출처: 유클리드 호제법 - 위키백과

 

 

문제 바로가기