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

문제 설명

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

 

제한사항 

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

 

 

 

풀이

최대공약수 : 유클리드 호제법

최소공배수: 두 input을 곱한 다음 최대공약수로 나눈 값

 

유클리드 호제법은 유명한 알고리즘 중 하나이다. 호제법이라는 말이 두 수가 서로 상대방 수를 나누어 원하는 수를 얻어내는 알고리즘이라는 뜻이다.

 

유클리드 호제법이라는 알고리즘은 처음 알았지만, 그것을 이용하기 위한 로직이 재귀함수를 쓰는 것이라 모처럼 정리해보았다.

 

const greatest = (a, b) => {
        if (b === 0) return a
        return greatest(b, a%b)
    }

 

b가 0이 아니면 계속 a를 반환하고, 자기 자신의 input을 b와 a%b로 지정하여 a%b가 0이 아니면 계속 연산이 일어나게 하는 로직이다. 재귀함수를 잘 활용해 본적이 없기에 선뜻 이해가 가지 않았지만 계속 활용하여 내 것으로 만들어야겠다는 생각을 했다.

 

최대공약수를 구했으니 최소 공배수는 따라온다. 결국 최종 풀이는 다음과 같다.

function solution(n, m) {
    var answer = [];
    const greatest = (a, b) => {
        if (b === 0) return a
        return greatest(b, a % b)
    }
    const least = (a, b) => (a * b) / greatest(a, b)
    return [greatest(n, m), least(n, m)];
}

 

 

 

그런데 다른 사람이 푼 풀이를 보니 for문으로 재귀함수를 대체하는 놀라운 풀이법이 있어 들고왔다.

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

 

 true/false 조건을 (r=a%b)로 판별하고 0이 나오면 자연스럽게 for문이 종료되는 방식이다. for문에 어지간히 익숙하지 않고는 생각해내기 어려운 방식이라 정리해봤다. 언제쯤 이런 로직도 생각해낼 수 있을까.