[프로그래머스] 최대공약수와 최소공배수 (Python)

문제 링크 (Level 1)

https://school.programmers.co.kr/learn/courses/30/lessons/12940?language=python3 

프로그래머스

 

나의 코드 (Python)

def solution(n, m):
    answer = []
    tmp1 = [] # n의 약수
    tmp2 = [] # m의 약수
    GCD = 0 # 최대공약수
    LCM = 0 # 최소공배수
    
    # 작은 수가 n으로 정렬
    if n > m:
        n, m = m, n
        
    # n의 약수 구하기
    for i in range(1, n+1):
        if n%i == 0:
            tmp1.append(i)
    # m의 약수 구하기
    for j in range(1, m+1):
        if m%j == 0:
            tmp2.append(j)
    # 최대공약수 구하기
    for a in tmp1:
        if a in tmp2:
            GCD = a
    # 최소공배수 구하기        
    if GCD != 1 and m % GCD == 0:
        LCM = m * n // GCD
    else:
        LCM = m * n
    
    # 결과
    answer.append(GCD)
    answer.append(LCM)
            
    return answer

 

1. 두 수를 비교해서 작은 수를 n으로 정렬 (반대여도 상관없음)

2. n의 약수 구하기

3. m의 약수 구하기

4. 최대공약수 구하기

--> tmp1에 수 중에서 tmp2에 포함 되어 있으면 최대공약수이고 tmp1는 1부터 시작하기 때문에 공통이 없으면 최대공약수는 1이 됨

5. 최소공배수 구하기

--> GCD(최대공약수)가 1이 아니면서 큰 수(tmp2)를 최대공약수로 나눴을 때 나머지가 0인 경우 두 수의 곱을 최대공약수로 나눔

--> 조건을 만족하지 않는 경우 두 수의 곱이 최소공배수