[코드테스트] 최대공약수와 최소공배수

최대공약수와 최소공배수

문제설명

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

제한사항

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

입출력 예

입출력 예 #1
위의 설명과 같습니다.

입출력 예 #2
자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

나의 풀이

18280

function solution(n, m) {

    let n_num = [];
    let n_min = [];
    let m_num = [];
    let m_min = [];
    let result = [];
    let max_divisor = [];
    let min_double = [];
    // 최대 공약수 구하기
    //첫 번째 약수를 구하고 n_num에 넣었다.
    for (let i = 1; i <= n; i++) {
        if(n % i === 0){
           n_num[i] = i
        }
    }//빈 배열 제거
    n_num = n_num.filter((v) => v > 0)
    //두 번째 약수를 구하고 m_num에 넣었다.
    for (let i = 1; i <= m; i++) {
        if(m % i === 0){
            m_num[i] = i
        }
    }//빈 배열 제거
    m_num = m_num.filter((v) => v > 0)
    //긴 배열을 기준으로 배열이 중복되는 값들을 새로운 배열로 넣었다. 그 중 가장 큰 값이 최대 공약수이다.
    if(n_num.length < m_num.length || n_num.length === m_num.length){
        max_divisor = m_num.filter(v => n_num.includes(v))
    }else if(n_num.length > m_num.length){
        max_divisor = n_num.filter(v => m_num.includes(v))
    }
    //result의 첫번째는 가장 큰 수(최대 공약수)를 넣었다.
    result[0] = max_divisor.sort((a,b) => a-b).pop();
    
    //최소 공약수 구하기
    //첫 번째 배열의 배수를 넣었다.
    for (let i = 0; i <= n*m; i+=n) {
        n_min[i] = i
    }//빈 배열 제거
    n_min = n_min.filter((v) => v > 0)
    //두 번째 배열의 배수를 넣었다.
    for (let i = 0; i <= n*m; i+=m) {
        m_min[i] = i
    }//빈 배열 제거
    m_min = m_min.filter((v) => v > 0)
    //긴 배열을 기준으로 배열의 값이 중복되는 값들을 새로운 배열로 넣었다. 그 중 가장 작은 값이 최소 공배수이다.
    if(n_min.length < m_min.length || n_min.length === m_min.length){
        min_double = m_min.filter(v => n_min.includes(v))
    }else if(n_min.length > m_min.length){
        min_double = n_min.filter(v => m_min.includes(v))
    }//result의 두번째 값은 가장 작은 수 (최소 공배수)를 넣었다.
    result[1] = min_double.sort((a,b) => b-a).pop();
    //결과 리턴
    return result
} 

다른 사람 풀이

원하는 값이 나올때까지 함수 안에 함수를 넣어 반복시키는 새로운 방식을 배웠다.


function gcdlcm(a, b) {
    //최대 공약수 의 값
    var gcd = calc_gcd(a, b);
    //최소 공배수의 값 구하기 
    var lcm = (a * b) / gcd;
  
      return [gcd, lcm];
  }
  //최대 공약수 함수 만들기
  function calc_gcd(a, b) {

    if (b == 0) return a;
        //나눈 나머지가 0이 될때까지 계속 나눈다... 유클리드 호제법!
      return a > b ? calc_gcd(b, a % b) : calc_gcd(a, b % a);
  }
  

좋은 웹페이지 즐겨찾기