프로그래머스 Lv.1 최대공약수와 최소공배수 (JavaScript)

자바스크립트로 프로그래머스 문제 풀기

문제

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

두 수의 최대공약수와 최소 공배수를 구하는 문제중 가장 기본 문제이다.

풀이

최대공약수, 최소공배수가 응용된 문제들이 좀 보여서 정리를 위해 기본 문제를 풀어보았다.

  최대공약수 / 최소공배수 란? : 주어진 수들의 공통 약수 / 배수에서 가장 큰 값 / 작은값 이다.

 

그래서 이 정의를 이용한 방법도 있으나, 유클리드 호제법을 사용하는것이 유리하므로 두가지 경우를 모두 정리해보았다.

 

for문 사용

function solution(n, m) {
    var answer = [];
    let a = Math.min(n, m);
    let b = Math.max(n, m);
    
    for(let i = a; i >= 1; i--) {
        if(a % i == 0 && b % i == 0) {
            return [i, (a * b / i)]
        }
    }
    return answer;
}

 

최대공약수를 먼저 찾으면 최소공배수는 간단하게 구할 수 있다 ( 최소 공배수는 n * m / 최대공약수)

최대이므로 주어진 두수 n, m  중 더 작은 수를 찾고, 작은 수를 1씩 감소시키면서 n, m 을 나누어떨어지게 하는 값을 찾으면 된다.

 

 

유클리드 호제법

유클리드 호제법을 간략하게 요약하면,

 두 수 a, b ( a > b) 의 최대공약수는 b, r ( r === a % b)의 최대공약수와 같다는 점을 이용한 알고리즘이다.

 긴 설명보다는 위키의 gif 가 가장 이해하기 좋은 것 같아서 첨부하였다.

 

이를 자바스크립트로 구현한 것은 아래와 같다. (gcd = Greatest common divisor)

// (a > b 라고 가정)
function gcd(a, b) {
	if (a % b === 0) return b;
    return gcg(b, a % b)
}

 

 

 

이를 사용하여 위의 문제를 풀어보면 아래와 같이 풀수 있다.

function solution(n, m) {
    var answer = [];
    let a = Math.min(n, m);
    let b = Math.max(n, m);
    const gcd = (x, y) => {
        return x % y === 0 ? y : gcd(y, (x % y))
    }
    let gd = gcd(b, a);
    answer = [gd, a * b / gd]
    
    return answer;
}