24. 최대공약수와 최소공배수

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

 

최대공약수 문제는 유클리드 호제법으로 푸는 게 정석입니다. 

전수조사(brute force)로는 시간제한에 걸려 통과할 수 없는 경우가 많습니다.

 

유클리드 호제법에 대해 아주 간략하게 설명을 드린 적 있습니다. 

https://comdoc.tistory.com/entry/%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98-%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98

 

파이썬

기본적인 풀이입니다.

def solution(n, m):
    g = n * m
    while m:
        if m < n:
            m, n = n, m
        m = m % n
    return [n, g // n]

반복문 안은 단순할수록 좋습니다.

3 % 4는 3이기 때문에 비교할 필요 없이,

반복문을 한 번 더 돌리면 제자리를 찾습니다. 

def solution(n, m):
    g = n * m
    while m:
        n, m = m, n % m
    return [n, g // n]

 

자바스크립트

재귀로 풀어봅니다. 

function solution(n, m) {
    let gcd = getGCD(n, m)
    let lcm = m * n / gcd
    return [gcd, lcm]
}

function getGCD(a, b){
    return a%b ? getGCD(b, a%b) : b
}

 

자바

class Solution {
    public int[] solution(int n, int m) {
        int g = m * n;
        int temp = 0;
        while (n > 0) {
            temp = m % n;
            m = n;
            n = temp;
        }
        return new int[]{m, g / m};
    }
}

 

고

func solution(n int, m int) []int {
	g := n * m
	for m > 0 {
		n, m = m, n%m
	}
	return []int{n, g / n}
}

 

코틀린

class Solution {
    fun solution(n: Int, m: Int): IntArray {
        var min = n
        var max = m
        var temp = 0
        val g = max * min
        while (min > 0) {
            temp = max % min
            max = min
            min = temp
        }
        return intArrayOf(max, g / max)
    }
}

 

C#

public class Solution
{
    public int[] solution(int n, int m)
    {
        int temp = 0;
        int g = n * m;
        while (m != 0)
        {
            n = n % m;
            temp = n;
            n = m;
            m = temp;
        }
        return new int[] { n, g / n };
    }
}