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

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

 

<제한사항>

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

<입출력 예시>

---

<내 풀이>

def solution(n, m):
    answer = []
    nm_divisor = [] #공약수 리스트
    nm_multiple = 0 #최소 공배수를 넣을 값
    
    n_divisor = []  #n의 약수
    m_divisor = []  #m의 약수
    
    i=1
    for i in range(1, n+1):  #n의 약수를 빈 리스트에 추가
        if n%i == 0:
            n_divisor.append(i)
    
    for i in range(1, m+1):  #m의 약수를 빈 리스트에 추가
        if m%i ==0:
            m_divisor.append(i)
            
    for i in range(len(m_divisor)): #최대 공약수를 빈 리스트에 추가
        for j in range(len(n_divisor)):
            if (m_divisor[i]) == (n_divisor[j]):
                nm_divisor.append(m_divisor[i])
    
    answer.append(max(nm_divisor)) #최대 공약수를 answer에 추가
    nm_multiple = int(n*m / answer[0]) #최소 공배수 구하기
    answer.append(nm_multiple) #최소 공배수를 answer에 추가
    
    return answer

최대공약수는 for문을 통해서 각각 약수를 구해주고 그 중에서 공약수를 따로 리스트에 넣어주고나서 그 공약수 리스트의 최소값을 가져오는 방법을 사용했다.

 

최소공배수는 "유클리드 호제법"이라는 계산 방법을 이용했다.

두 수를 곱해주고 나서 그 값을 최대 공약수로 나눠주면 최소 공배수가 나온다는 공식을 검색도중에 알아냈다.

 nm_multiple = int(n*m / answer[0]) #최소 공배수 구하기

위와 같이 공식을 이용해서 answer 리스트에 추가시켜주어 답을 구했다.

 

<다른사람의 풀이>

def gcdlcm(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

최대 공약수를 구하는 방법에서 구현해낸 알고리즘이 나와는 차원이 다르다...^^