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

문제설명

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

---

제한조건

• 두 수는 1이상 1000000이하의 자연수입니다.

---

입출력예시

n	m	return
3	12	[3, 12]
2	5	[1, 10]

---

처음풀이

function yacksu(n){
    let arr = []
    for(let i = 1; i <= Math.sqrt(n); i++){
        if(n % i === 0){
            if(i === n){
                arr.push(i)
            } else{
                arr.push(i)
                arr.push(n/i)
            }
        }
    }
    return arr
}
function solution(n, m) {
    var answer = [];
    let n_arr = yacksu(n).sort((a,b)=>b-a)
    let m_arr = yacksu(m).sort((a,b)=>b-a)
    
    for(let i = 0; i < n_arr.length; i++){
        if(m_arr.includes(n_arr[i])){
            answer.push(n_arr[i])
            break
        }
    }
    answer.push((n*m/answer[0])
    
    return answer;
}

---

수정된 풀이

function solution(n, m) {
    const yacksu = (a,b)=>{
        if(b === 0) return a
        return yacksu(b,a%b)
    }
    return [yacksu(m,n),(n*m)/yacksu(m,n)]
}

---

설명

처음에는 약수를 일일이 각 수 별로 반복무을 돌면서 리스트 업을 하고 거기서 비교해 가장 큰 약수를 찾아내는 방식으로 해결했는데, 팀원들과 얘기를 하다가 '유클리드 호제법'을 이용한 재귀함수를 사용하면 아주 간단히 해결할 수 있다는 사실을 알게되었다.

유클리드 호제법 : 호제법은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘으로, 유클리드 호제법은 a와 b의 최대공약수는 a와 r(=a%b)의 최대공약수가 같음을 이용해 호제법을 사용하는 알고리즘이다.

즉, 한 수로 다른 한 수를 나눈 나머지가 0이 될 때까지 재귀함수를 반복하면, 최대공약수를 얻을 수 있는 것이다.

알고리즘 문제를 푸는데에 수학적인 지식도 중요하다는 것을 자주 느끼게 되는 것 같다.