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

---

문제 설명

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

 

제한 사항

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

---

 

나의 풀이)

1. 두 수를 n, m이라고 하자.

2. 먼저, n, m을 리스트(lst)에 넣어준다.

3. 최대공약수 구하기

- 반복문을 1부터 작은 수 min(lst)까지 반복한다.

- max(lst), min(lst)를 각각 i로 나누었을 때 나머지가 0이면 나누어 떨어진다는 것이다.

즉, 두 수를 i로 나눴을 때 나머지가 0인 i가 두수의 공약수라는 점을 이용해 코드를 짜보았다.

가장 큰 i값을 result 결과 리스트에 append 해준다.4. 최소공배수 구하기- 조건 1) max(lst)를 min(lst)로 나누었을 때 나머지가 0이면 최대공배수는 max(lst)- 조건 2) max(lst)를 최대공약수(max_)로 나누었을 때 나머지가 0이면 최대공배수는 min(lst) * (max(lst)//max_)- 조건 3) 위의 두 경우가 아니면 n*m이 최대공배수가 된다.

 

def solution(n, m):
    lst = [n, m]
    result = []
    
    #최대공약수
    for i in range(1, min(lst)+1):
        if max(lst) % i == 0 and min(lst) % i == 0:
            max_ = i
    result.append(max_)
    
    #최소공배수
    if max(lst) % min(lst) == 0:
        result.append(max(lst))
    elif max(lst) % max_ == 0:
        result.append( min(lst) * (max(lst)//max_))
    else:
        result.append(n*m)

    return result

내가 봐도 정말 복잡한 코드... 뭘 이렇게 어렵게 생각했을까 ㅠㅠ

다른 사람들이 푼 간단한 코드를 보니 또 너무 쉽게 푸는 문제였다...!

 

 

가장 간단히 푼 두개의 코드를 가져왔다.

다른 사람 풀이1)

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

다른 사람 풀이2)

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

 

---

https://school.programmers.co.kr/learn/courses/30/lessons/12940

 

프로그래머스