프로그래머스 문제풀이 12

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]을 리턴해야 합니다.


문제풀이

function solution(n, m) {
    //최대공약수 : 두 수의 공통되는 약수 중 제일 큰 수
    //최소공배수 : 두 수의 공통되는 배수 중 제일 작은 수
    const biggest = Math.max(n,m)
    //최대공약수 구하기
    let max = 0; //공약수 중 제일 큰 수만 저장
    for(let i = 1; i <= biggest; i++){
        if(n % i ===0  && m % i ===0){
            max = i
        }
    }
    //최소공배수 구하기
    let min = 0;
    for(let i = biggest; i <= n * m; i += biggest){
        if(i % Math.min(n,m) === 0 ){
            min = i
            break;
        }
    }
    return[max, min]
}

리팩토링

function solution(n, m) {
    //최대공약수 : 두 수의 공통되는 약수 중 제일 큰 수
    //최소공배수 : 두 수의 공통되는 배수 중 제일 작은 수
    const biggest = Math.max(n,m)
    //최대공약수 구하기
    let max = 0; //공약수 중 제일 큰 수만 저장
    for(let i = 1; i <= biggest; i++){
        if( !(n % i) && !(m % i) ){
            max = i
        }
    }
    //최소공배수 구하기
    for(let i = biggest; i <= n * m; i += biggest){
        if( !(i % Math.min(n,m)) ){
        return [max, i]
        }
    }
    return[max, min]
}

접근방법
1.최대공약수 먼저 구해본다.
2.n과 m의 큰 수를 저장할 수 있는 변수를 만든다.
3. n과 m의 중 큰 수를 담아본다.
const biggest = Math.max(n,m)
4. 제일 큰숫자가 포함되거나 작은숫자까지 반복문을 돌린다.
5. i값으로 가져오는 숫자들을 n과 m으로 나눴을 때의 나머지값을 구해본다.
console.log(i , n % i , m % i)
6. max에 담아서 계속해서 갱신
7. 최소공배수 중에서 제일 작은 숫자를 저장
8. 나누었을 때 떨어진다면 배수
9. 원하는 시점에서 함수를 종료시켜준다.


다른방법 - 유클리드 호제법

function solution(n, m) {
    // 유클리드 호제법 : 최대공약수를 구하기 위한 공식
    // a를 b로 나눴을 때 (a가 b 보다 큰 경우) === 큰 수에서 작은 수를 나눴을 때 
    // 나머지 값이 0이 된다면, 작은 수(b)가 최대공약수가 된다.
    // 나누어 떨어지지 않는다면, 큰 수(a)에는 작은수(b)가 들어오고
    // 작은 수(b)에는 나머지 값이 들어온다.
    // a와 b를 나누는 과정을 반복했을 때 , 나머지 값이 0이 되면 작은 수(b)가 최대공약수가 된다.
    let a = Math.max(n,m) //제일 큰 수
    let b = Math.min(n,m) //제일 작은 수 
    let r // a를 b로 나웠을 때 나머지 값
    while( (a % b) > 0 ){
        r = a % b; // 두 수를 나눴을 때의 나머지 값을 저장
        a = b; // 큰 수에는 나눴던 작은 수를 다시 넣어준다.
        b = r; // 작은 수에는 나머지 값이 다시 들어온다.
        console.log(a,b,r)
    }
    // 최소공배수는 두 수(a,b)를 곱한 수에 최대공약수를 나눈 몫의 값
    return [ b , (n * m) / b]
}