프로그래머스 JavaScript - 최대공약수, 최소공배수 구하기

문제

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, 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 = [];
    let max = []
    //n이 더 클때
    if(n>m){
        for(i=1;i<=m;i++){
            if(n%i == 0 && m%i == 0){
                max.push(i)
            }
        }
        if(n%m == 0){
            answer.push(n)
        }else{
            answer.push(n*m)
        }
    }
        
    //m이 더 클때    
    if(m>n){
        for(i=1;i<=n;i++){
            if(n%i == 0 && m%i == 0){
                max.push(i)
            }
        }
        if(m%n == 0){
            answer.push(m)
        }else{
            answer.push(n*m)
        }
    }
    console.log(max) //공약수만 포함되어있는 배열, 맨 뒤에있는걸 answer에 넣는다
    console.log(min) //공배수!
    
    answer.unshift(max[max.length - 1])

    return answer;
}

먼저 n과 m의 크기 비교를 해서 각각의 상황으로 나눠주었다.

최대공약수는 공통된 i로 n과 m을 나누었을때 떨어지는 수를 max 배열안에 넣고 맨 뒤 숫자를 answer안에 넣는 식으로 처리했다.

그리고 최소공배수는 작은수로 큰수를 나누었을때 딱 맞아 떨어진다면 큰수를 바로 answer 배열안에 넣도록 했고, 떨어지지 않는 경우에는 n * m을 answer안에 넣는식으로 처리했다. 사실 n * m 경우는 틀릴거라고 예상은 했는데 당장 좋은 생각이 나지 않아 이런식으로 처리했다.

주어진 테스트케이스는 통과했으나 채점해보니 당연히 통과되지 않았다.

그래서 테스트 케이스를 추가하며 최소공배수를 구하는 공식이 무엇일지 생각해 보았다. 

기존 만든 코드로 통과되지 않는 케이스를 추가해 보았다.

이 둘의 공통점은 1을 제외한 최대공약수가 존재한다는 것이다.

그리고 작은수를 최대공약수로 나눈 수(4, 7)를 큰수에 곱하면 최소공약수가 나온다는걸 알게되었다.

function solution(n, m) {
    var answer = [];
    let max = []
    //n이 더 클때
    if(n>m){
        for(i=1;i<=m;i++){
            if(n%i == 0 && m%i == 0){
                max.push(i)
            }
        }
         let y = max[max.length - 1]
        if(n%m == 0){
            answer.push(n)
        }else if(y !== 1){
            answer.push(m/y*n)
        }else{
            answer.push(n*m)
        }
    }
        
    //m이 더 클때    
    if(m>n){
        for(i=1;i<=n;i++){
            if(n%i == 0 && m%i == 0){
                max.push(i)
            }
        }
         let y = max[max.length - 1]
        if(m%n == 0){
            answer.push(m)
        }else if(y !== 1){
            answer.push(n/y*m)
        }else{
            answer.push(n*m)
        }
    }
    answer.unshift(max[max.length - 1])
    return answer;
}

else if로 최대공약수가 1이 아닌 경우를 추가해주었더니 모든 테스트에서 통과되었다!

 

다른풀이

function gcdlcm(a, b) {
    var r;
    for(var ab= a*b;r = a % b;a = b, b = r){}
    return [b, ab/b];
}

 

 

for문을 이렇게도 쓸 수 있구나라는걸 알아간다..