[프로그래머스 스킬체크 레벨 1] 최대공약수와 최소공배수 풀이 및 설명 - 자바스크립트[JavaScript]

https://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]

 

기본 제공 틀

 

function solution(n, m) {
    var answer = [];
    return answer;
}

 

풀이 [JavaScript]

 

728x90

우선, 최대공약수와 최소공배수의 개념대로 로직을 짜야겠다고 생각했다.

들어온 값에서 상대적으로 큰 값을 뒤로 m으로 지정하고자, 자바스크립트에서 쉽게 swipe할 수 있는 방식인 [n, m] = [m, n]을 이용하여 큰값을 m으로 지정하게 해주었다.

먼저 이렇게 값을 지정해준 후, 1부터 상대적으로 작은 수인 n까지의 값을 돌면서 n과 m 두 숫자가 다 나머지가 없이 잘 나누어 떨어지는 숫자를 찾아보았다.

그 중 가장 큰 수가 약수이기 때문에, n까지의 숫자 중 가장 마지막에 common에 들어간 나머지 값이 약수가 되게 로직을 짜 보았다.

그렇게 구해진 약수를 answr에 넣었고, 약수가 n그 자체라면 그 common그 자체와 common으로 나눈 m의 값을 곱하면최소공배수가 되고, 약수가 n이 아니라면, 약수(common)으로 m을 나눈 값과, n으로 나눈 값 그리고 약수 그 자체 세가지를 곱해야 최소공배수가 나오므로 아래와 같이 설계하게되었다.

function solution(n, m) {
    var common = 1;
    var answer = [];
    if(n>m) [n,m] = [m,n];
        for(var i=1; i<=n; i++){
            if(n % i ===0 && m % i ===0){
                common = i;
            }
        }
        answer.push(common);
        if(common !== n){
            answer.push((m/common)*(n/common)*common);
        }else{
            answer.push(common*(m/common));
        }
    return answer;
}

위에서 푼 방식은 가장 기본적인 방식이고 아래는 재귀함수를 사용하여 짠 방식이다.

최대공약수를 짜는 함수를 따로 생성한 것인데, 재귀함수를 설명해보자면, b가 0이면 false고, 0이 아닌 숫자가 true인데, !b이기때문에, 반대로 0일대 true가 되는 방식이다. true가 아니므로, 다시 getGcd라는 재귀함수로 호출을 하게된다.

3과 12를 예로 들어 설명해보자면, 처음에 (a, b)에서 b는 0이 아니므로 getGcd를 통해, getGcd는 (b, a%b)로 인해, (12, 3)이 된다, 그러므로 다시  호출되는 getGcd(a,b)는 getGcd(12, 3)이 된다. b는 0이 아니므로, getGcd(3, 12%3)은 getGcd(3, 0)가 되고, b가 0이 되므로, true가 나와서 a값은 3이 된다.

 

그러므로, 3과 12의 최대공약수는 3이고, 최소공배수는 두 수의 곱에서 최대공약수로 나눠서 구할 수 있으므로, 아래와 같은 로직을 짜면 최대공약수와 최소공배수를 리턴할 수 있다.

 

이번 방식으로는 재귀함수를 사용하는 방식에 조금 익숙해질 수 있었던 것 같다.

 

3 12 false 3 12 3 false 0 3 0 true NaN

function solution(n, m) {
    var gcd = getGcd(n, m);
    var lcm = (n * m) / gcd;
    return [gcd, lcm];
}

function getGcd(a, b) {
    return !b ? a : getGcd(b, a % b);
}

채점 결과 [JavaScript]