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

출처/프로그래머스

● 문제 설명

 

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요.

배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다.

예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

 

● 제한 사항

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

 

● 입출력 예

 

n	m	return
3	12	[3, 12]
2	5	[1, 10]

● 입출력 예 설명

 

입출력 예 #1
위의 설명과 같습니다.

 

입출력 예 #2
자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

 

---

나의 풀이

 

function solution(n, m) {
    const getGCD = (num1, num2) => (num2 > 0) ? getGCD(num2, num1%num2) : num1;
    const getLCM = (num1, num2) => (num1 * num2) / getGCD(num1, num2);
    
    return [getGCD(n, m), getLCM(n, m)];
}

 

유클리드 호제법을 사용하여 최소공배수와 최대공약수를 구했다.

 

유클리드 호제법

두 양의 정수 a, b (a > b)에 대하여 a = r (mod b) 라면, a, b의 최대공약수는 b, r의 최대공약수와 같다.
즉, r = 0 이라면, a, b의 최대공약수는 b가 된다.

 

num1을 num2로 나눈 나머지를 r이라고 한다면, GCD(num1, num2) = GCD(num2, r)과 같고,

r이 0이라면 r에 상응하는 num2가 num1과 num2의 최대공약수라는 것이다.

 

예를 들어, num1 = 24, num2 = 20 이라고 가정했을 때, 

GCD(24, 20) = GCD(20, 4) 가 될 것이고, 다시 GCD(20, 4) = GCD(4, 0) 이 되어,

24와 20의 최대공약수는 4가 된다.

 

만약 위의 '나의 풀이' 처럼 num1 < num2 의 상황이라면, 처음 호출되는 재귀 함수에서 자동으로 swap 된다.

GCD(3, 12) = GCD(12, (3%12=3)) = GCD(12, 3)

 

 

최소공배수는 num1 * num2 = GCD * LCM 과 같다는 원리를 이용하여,

LCM = (num1 * num2) / GCD 가 된다.

 

---

후기

 

처음 코드는 for문과 if문을 활용하여 작성했는데,

공부가 제대로 되지도 않는 것 같았고, 이런 문제들은 분명 공식이 있을 거라 생각해서 찾아보다가 발견한 것이 유클리드 호제법이었다.

 

보면서 참 대단하다고 느꼈고, 충격이 컸던 만큼 뇌리에 강하게 박혀서

최소공배수와 최대공약수는 사용해야 할 상황이 생기더라도, 오늘의 기억을 떠올리며 쉽게 작성할 수 있을 것 같다.