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

프로그래머스

 

1. 문제

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, 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]을 리턴해야 합니다.

 

2. 정답 풀이

// 약수 배열 리턴
const getDiv = (num) => {
    let arr = []
    for(let i=1; i<=num; i++) {
        if(num % i === 0) arr.push(i)
    } 
    return arr
} 
// 약수 배열들을 비교해 최소공배수(가장 큰 약수)를 리턴한다.
const getMin = (a1, a2) => {
    const filtered = a1.filter(num => a2.includes(num))
    return filtered[filtered.length-1]
}

function solution(n, m) {
    let div1 = getDiv(n);
    let div2 = getDiv(m);
    let a = getMin(div1, div2);
    let b;
    let num = 1;
    // 두 수가 1이상 자연수 -> 1부터 순회하며 최소 공약수를 찾고 찾으면 순회를 종료하고 리턴
    while(1) {
        if(num % n === 0 && num % m === 0) {
            b = num;
            break;
        }
        num++
    }
    return [a,b]
}

 

3. 최종 풀이

풀이 전략

• 유클리드 호제법 이용

최대공약수 : 2개의 자연수 a, b(a > b)에 대해서 a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

최소공배수: a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수를 나눈 것과 같다.

const getMaxDividor = (n,m) => {return m ? getMaxDividor(m, n % m) : n}
const getMinDividor = (n,m) => {return (n * m) / getMaxDividor(n,m)}
function solution(n, m) {
    return [getMaxDividor(n,m), getMinDividor(n,m)]
}

 

 

 

수학 공식이나 증명을 이용하니까 코드가 너무 쉽고 간결해진다...😱
알고리즘 풀이 많이 해보면서 기억할 수 있는 공식이나 증명들은 외워두면 좋을 것 같다!

 

 

[프로그래머스] 옹알이(2) (LV1 - JavaScript)

 

[프로그래머스] 덧칠하기 (LV1 - JavaScript)