[프로그래머스] 최대공약수와 최소공배수 - 파이썬(python)

 

 

나의 풀이

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

최대공약수 -> 1부터 min(n,m) 까지 돌면서 
n,m 이 나눴을 때 둘다 나머지가 0인 숫자

최소공약수 -> max(n,m) 이상인 최대공약수의 배수를 확인하면서,
n,m둘다 나머지를 0으로 나누는 숫자

 

 

 

다른 풀이

def gcd(a, b):
    return b if a % b == 0 else gcd(b, a % b)

def lcm(a, b):
    return int(a * b / gcd(a, b))


def gcdlcm(a, b):
    answer = [gcd(a,b), lcm(a,b)]

    return answer

# 아래는 테스트로 출력해 보기 위한 코드입니다.
print(gcdlcm(3,12))

유클리드 호제법을 이용한 풀이방법이라는데,,,,

나는 이렇게 생각을 못할 것 같다,,

 

12 와 54를 예시로 들자.

gcd ) 12 54 ->  54 6 -> return 6

lcm ) 12 * 54 / 6 = 108