♡̈ 17. 프로그래머스:: 최대공약수와 최소공배수

 

최대공약수를 구하는 방법은 몇 번 스쳐지나가듯 봤는데,

최소공배수에 대한 부분은 잘 알지 못했다.

 

그래서 우선 최대공약수와 최소공배수의 관계를 정의해보았다.

최대공약수와 최소공배수의 관계

정수론 (1) - 최대공약수, 최소공배수, 유클리드 호제법

 

최대공약수: 두 정수 a, b의 공통 약수
최소공배수: 두 정수 a, b의 공통 배수 중 가장 작은 값

 

최대공약수는 유클리드 호제법으로 구할 수 있다.

1. 정수 a를 b로 나눈 나머지 r을 구한다.
2. a = b, b = r로 갱신한다.
3. 나머지가 0이 될 때까지 반복한다.

 

최소공배수는 최대공약수를 활용해 구할 수 있다.

1. 정수 a, b를 곱한 mul을 구한다.
2. mul을 최대공약수로 나눈다.

 

이렇게 찾은 정수론으로 구하는 코드는 다음과 같다.

function solution(a, b) {
    function gcd(x, y) {
        while (y !== 0) {
            let temp = y;
            y = x % y;
            x = temp;
        }
        return x;
    }

    function lcm(x, y, gcdValue) {
        return (x * y) / gcdValue;
    }

    const gcdValue = gcd(a, b);
    const lcmValue = lcm(a, b, gcdValue);

    return [gcdValue, lcmValue];
}

 

그러다가 미친 코드를 봤다.

function gcdlcm(a, b) {
    var r;
    for(var ab= a*b;r = a % b;a = b, b = r){}
    return [b, ab/b];
}

 

구현 로직은 똑같은데 더 간결한 코드다.

for문 내부에 실행 구문이 없다는 부분에서 큰 의의가 있다.

r = a % b

 

이 조건 검사절 때문인데, 0이 되면 알아서 종료되기 때문이다.

증감표현식에 두 개가 들어갈 수 있단 것도 처음 배웠다.