[programmers] [Python] 최대공약수와 최소공배수

코딩테스트 연습 - 최대공약수와 최소공배수 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

문제

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

제한 사항

두 수는 1이상 1000000이하의 자연수

---

접근법

1. 두 수를 비교해 큰 값을 찾는다
2. 두 수의 최대공약수를 구한다.
3. 두 수의 최소공배수(두 수의 곱을 최대공약수로 나눈 것)를 구한다.

아래의 네 가지 풀이는 최대공약수를 구하는 과정을 다르게 해서 풀었다.

 

풀이 1 (for문 이용)

1. 두 수가 모두 짝수면 최대 공약수는 짝수, 아니면 최대공약수는 홀수임을 이용 => start, answer
1-1 for문 안에 들어가지 않거나, for문을 모두 돌아도 만족하지 않을 경우의 최대공약수 => answer
    (둘 다 짝수일 경우 2, 아닐 경우 1)
2. a와 b의 약수를 구할 때마다 answer를 갱신해줌

def solution(n, m):
    def find_divisor(a, b):
        start = answer = 2 if a%2 == b%2 == 0 else 1
        for i in range(start+2, b+1, 2):
            if a%i == b%i == 0:
                answer = i
        return answer
    if n < m:
        n, m = m, n
    max_divisor = find_divisor(n, m)
    min_multiple = n * m // max_divisor
    return [max_divisor, min_multiple]

# 결과
테스트 1 〉	통과 (0.01ms, 9.98MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (0.01ms, 10.1MB)
테스트 4 〉	통과 (0.01ms, 10.2MB)
테스트 5 〉	통과 (0.01ms, 10.2MB)
테스트 6 〉	통과 (0.00ms, 9.97MB)
테스트 7 〉	통과 (0.01ms, 10.1MB)
테스트 8 〉	통과 (0.01ms, 10.1MB)
테스트 9 〉	통과 (0.01ms, 9.97MB)
테스트 10 〉	통과 (0.01ms, 10.1MB)
테스트 11 〉	통과 (0.04ms, 10.1MB)
테스트 12 〉	통과 (0.17ms, 10.2MB)
테스트 13 〉	통과 (0.10ms, 10.1MB)
테스트 14 〉	통과 (0.16ms, 10.3MB)
테스트 15 〉	통과 (0.07ms, 10.1MB)
테스트 16 〉	통과 (0.07ms, 10.1MB)

 

풀이 2 (for문 이용)

1. 두 수가 모두 짝수면 최대 공약수는 짝수, 아니면 최대공약수는 홀수임을 이용 => answer
1-1 for문 안에 들어가지 않거나, for문을 모두 돌아도 만족하지 않을 경우의 최대공약수 => answer
    (둘 다 짝수일 경우 2, 아닐 경우 1)
2. 반복문의 범위는 b가 홀수면 b -> 3, a만 홀수면 b-1 -> 3, 둘다 짝수면 b -> 4 (끝값 포함)
3. 큰 수에서 작은 수로 가면서 최대공약수를 찾으면 함수 종료

def solution(n, m):
    def find_divisor(a, b):
        if b%2:
            answer, start = 1, b
        elif a%2 == 0:
            answer, start = 2, b
        else:
            answer, start = 1, b-1
        for i in range(start, 2, -2):
            if a%i == b%i == 0:
                return i
        return answer
    if n < m:
        n, m = m, n
    max_divisor = find_divisor(n, m)
    min_multiple = n * m // max_divisor
    return [max_divisor, min_multiple]

테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.00ms, 10MB)
테스트 3 〉	통과 (0.00ms, 9.98MB)
테스트 4 〉	통과 (0.01ms, 10MB)
테스트 5 〉	통과 (0.00ms, 10.2MB)
테스트 6 〉	통과 (0.00ms, 10.1MB)
테스트 7 〉	통과 (0.00ms, 10.2MB)
테스트 8 〉	통과 (0.00ms, 10.3MB)
테스트 9 〉	통과 (0.00ms, 10.1MB)
테스트 10 〉	통과 (0.00ms, 9.95MB)
테스트 11 〉	통과 (0.03ms, 10.3MB)
테스트 12 〉	통과 (0.09ms, 10.1MB)
테스트 13 〉	통과 (0.05ms, 10.1MB)
테스트 14 〉	통과 (0.10ms, 10.2MB)
테스트 15 〉	통과 (0.03ms, 10MB)
테스트 16 〉	통과 (0.06ms, 10.1MB)

 

풀이 3 (유클리드 호제법 이용)

유클리드 호제법이란?

https://ilwol-developer.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95-%ED%8C%8C%ED%97%A4%EC%B9%98%EA%B8%B0

1. 큰 수(a)를 작은 수(b)로 나누는 것을 반복하며, 나머지가 0이 될 때 반복문 종료
2. a를 b로 나눈 나머지를 a에 저장
3. a가 0이 아닐 경우, a와 b의 값을 교환해줌 (a가 큰 값, b가 작은 값이 될 수 있도록 하는 과정)

def solution(n, m):
    def find_divisor(a, b):
        while a:
            a %= b
            if a == 0:
                return b
            a, b = b, a
    if n < m:
        n, m = m, n
    max_divisor = find_divisor(n, m)
    min_multiple = n * m // max_divisor
    return [max_divisor, min_multiple]

테스트 1 〉	통과 (0.00ms, 10MB)
테스트 2 〉	통과 (0.00ms, 10.1MB)
테스트 3 〉	통과 (0.00ms, 10.2MB)
테스트 4 〉	통과 (0.00ms, 10.1MB)
테스트 5 〉	통과 (0.00ms, 10.1MB)
테스트 6 〉	통과 (0.00ms, 10.1MB)
테스트 7 〉	통과 (0.00ms, 10.1MB)
테스트 8 〉	통과 (0.00ms, 10.2MB)
테스트 9 〉	통과 (0.00ms, 10.3MB)
테스트 10 〉	통과 (0.00ms, 10.1MB)
테스트 11 〉	통과 (0.00ms, 10.3MB)
테스트 12 〉	통과 (0.01ms, 10.2MB)
테스트 13 〉	통과 (0.00ms, 9.92MB)
테스트 14 〉	통과 (0.00ms, 10MB)
테스트 15 〉	통과 (0.00ms, 10.1MB)
테스트 16 〉	통과 (0.00ms, 10.2MB)

 

풀이 4 (제곱근 이용)

1. 반복문의 끝값을 작은 수의 제곱근의 정수형을 이용해 결정해줌 => end
1-1. 16에서 16 = 1 * 16 = 2 * 8 = 4 * 4이므로, 1에서 16까지 16번 반복해 약수를 찾는 것보다,
     1에서 4까지 네 번 반복하는 게 더 효율적임
2. 1에서 end-1까지 b의 약수를 찾은 후, a의 약수인지 판별 => i, quot
2-2. i가 작은 수에서부터 시작하므로 quot은 큰 수에서부터 시작하고, 항상 i <= quot임

def solution(n, m):
    def find_divisor(a, b):
        from math import isqrt
        answer = 1
        end = isqrt(b) + 1
        for i in range(1, end):
            quot = b//i
            if b % quot == 0:
                if a % quot == 0:
                    return quot
            if b % i == 0:
                if a % i == 0:
                    answer = i
        return answer
    if n < m:
        n, m = m, n
    max_divisor = find_divisor(n, m)
    min_multiple = n * m // max_divisor
    return [max_divisor, min_multiple]