[level 1] 최대공약수와 최소공배수

문제

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

 

문제 풀이 접근법1

처음에는 유클리드 알고리즘을 사용해서 문제를 푸는 방법을 생각했다.

 

1) n % m == r(단, n > m)일때, n과 m의 최대 공약수는 m과 r의 최대 공약수와 같고 만약 m == 0이면 m이 n과 m의 최대 공약수가 된다. 

2) 두 수의 곱은 최대 공약수와 최대 공배수의 곱이므로 두수의 곱을 최대 공약수로 나누면 최대 공배수를 구할 수 있다. 

def solution(n, m):
    answer = []
    if n < m:
        tmp = n
        n = m
        m = tmp

    r = n % m

    while(True):
        if r == 0:
            gcd = m
            answer.append(gcd)
            break
        n = m
        m = r
    
    answer.append(int((n*m)/gcd))

    return answer

두번 째 테스트 케이스에서 실행 초과가 걸렸다...ㅎ

아마 while이 무한 루프여서 그랬던 것 같다. 

 

 

문제 풀이 접근법2

위와 같이 유클리드 호제법을 사용하였으나 위에서도 결국 r==0이 되면 break로 탈출하게 하였으므로 이번에는 while문 자체에 조건을 걸었다.

def solution(n, m):
    
    answer = []
    
    def gcd(a, b):
        while b > 0:
            a, b = b, a % b
        return a
    
    answer.append(gcd(n, m))
    answer.append(n*m / answer[0])

    return 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

# 아래는 테스트로 출력해 보기 위한 코드입니다.
print(gcdlcm(3,12))

유클리드 알고리즘에서 a>b라는 전제 조건이 있어서 사실 위의 내 코드를 작성하면서 

내심 걱정했는데

max, min값으로 값을 결정해준게 인상 깊었다.