프로그래머스 1단계 - 최대공약수와 최소공배수

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) {
    let answer = [];
    let max_val = Math.max(n,m);
    let min_val = Math.min(n,m);
    let gcd, lcm; // gcd : 최대공약수, lcm : 최소공배수
    let r = max_val % min_val; // r은 나머지
    if(!r) gcd = min_val; // 만약 r이 0이면 두 수중 작은수가 최대공약수
    while(!gcd){ // 위에서 안나누어 떨어지면 gcd가 undefined 겠죠
        max_val = min_val; // 이 루프에서 두 수중 작은수가 큰수가 되고
        min_val = r; // 작은수는 위에서 구했던 나머지가 된다.
        r = max_val % min_val; // 나머지는 위랑 마찬가지로 max_val % min_val이 되고
        if(!r){ // r이 0이되는 순간 gcd가 결정되고 끝난다.
            gcd = min_val;
            break;
        };
    }
    lcm = (n / gcd) * (m / gcd) * gcd; // 최소공배수는 두 수를 각각 최대공약수로 나눈 몫과 최대공약수를 곱해주면 나오죠
    // 초등학교 때 했던거 있잖아요.
    return [gcd, lcm];
}

리뷰

순서는 다음과 같다
1. min_val, max_val, gcd(최대공약수) lcm(최소공배수) 초기화 시키고
2. max_val % min_val 해줍니다. 0이면 작은수가 최대공약수
3. 안나누어 떨어지면 max_val % min_vald === 0 이 될 때 까지 반복해야합니다.
4. 여기서 max_val은 전에 min_val이 었던 값, min_val은 max_val % min_vald이 됩니다.
5. r이 0이 되는 순간, gcd = min_val이 되고 루프를 탈출합니다.
6. lcm은 초등학교 때 구했던 방식대로 각각의 수를 gcd로 나눈 몫을 곱하고 마무리로 gcd 곱해주면 되겠죠?

총평 : 최대공약수만 구하면 최소공배수는 나오는데, 최소공약수를 구하는 로직이 쉽지 않네요, 그렇지 않은가요?

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