Programmers / 최대공약수와 최소공배수 찾기 / Python

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 최대공약수와 최대공배수

문제 사이트: https://programmers.co.kr/learn/courses/30/lessons/12940

---

나의 풀이(시간초과)

def solution(n, m):
    
    num = [n,m]
    a = []
    b = []
    #공통 약수 찾기
    for i in range(1,max(num)):
        if n % i == 0 and m % i == 0:
            a.append(i)
    #공배수 찾기
    for i in range(1,m*n+1):
        for j in range(1,m*n+1):
            if m * i == n * j:
                b.append(m*i)
            
            
    answer = [max(a),min(b)]
    return answer

아마 중첩 for문때문에 시간 초과를 한게 아닌가 싶다

 

모범답안

def solution(a, b):

    c, d = max(a, b), min(a, b)
    t = 1

    while t > 0:

        t = c % d
        c, d = d, t

    answer = [c, int(a*b/c)]

    return answer

while문을 이용해서 구현했군.. 

마지막 answer에 최소공배수 앞서 구한 최대공약수로 나눈 것까지 완벽하다..

---

※ 알아야 할 것

- 최소공배수는 두 수의 곱에 최대공약수를 나눈 값과 같다.