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

📝 문제

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

[제한사항]
- 두 수는 1이상 1000000이하의 자연수입니다.

 

문제링크

프로그래머스

---

✅ 풀이

import math
def solution(n, m):
    answer = []
    ns = []
    ms = []

    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0 and i not in ns:
            ns.append(i)
            ns.append(n//i)

    for i in range(1, int(math.sqrt(m))+1):
        if m % i == 0 and i not in ms:
            ms.append(i)
            ms.append(m//i)

    li = [k for k in ns if k in ms]
    answer.append(max(li))
    answer.append(n*m//answer[0])

    return answer

💡 처음엔 시간초과가 의식되어서 소인수분해로 접근하는 방법을 이용했는데,
어디선가 반례가 걸리는 것을 해결하지 못해 속는셈치고 일일이 약수를 구했다.
공약수를 따로 모아 최대공약수를 구하고, 최대공약수를 활용해 최소공배수를 구해주었다.