[JavaScript] 프로그래머스 level1 #최대공약수와 최대공배수

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

프로그래머스

---

 

문제 설명

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

 

 

 

제한 사항

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

 

 

 

입출력 예

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

 

 

 

해결 방법

최대공약수는 유클리드 호제법이라는 알고리즘을 이용하면 쉽게 해결할 수 있었다.

 

유클리드 호제법이란?

a가 b보다 클 때 a를 b로 나눴을 때 나머지를 r이라고 한다면 a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

그러면 b와 r의 최대공약수는 b를 r로 나눴을 때 나머지를 r2라고한다면 r과 r2의 최대공약수와 같다. 

...

이런 식으로 진행하다가 나머지가 0이 됐을 때 나누는 수가 a와 b의 최대공약수가 된다.

a % b ... r
b % r ... r2
r % r2 ... r3
r2 % r3 ...0

a와 b의 최대공약수는 r3이 되는 것이다.

 

최소공배수는 'a * b / a와 b의 최대공약수' 이다.

 

 

 

전체 코드

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

 

 

 

다른 해결 방안 코드

https://velog.io/@qmasem/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98%EC%99%80-%EC%B5%9C%EC%86%8C-%EA%B3%B5%EB%B0%B0%EC%88%98-%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8

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