Javascript / SQL - 17

1. Javascript

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

• 프로그래머스 문제를 푸는 중 위의 문제를 아래와 같이 처음에 풀었었다.

function solution(n, m) {
    let answer = [];
    let nDivide = [];
    let mDivide = [];
    let nMulti = [];
    let mMulti = [];
    let nmMulti = [];
    let nmDivide = [];
    if (n < 1 || m < 1 || n > 1000000 || m > 1000000) {
        console.log('error');
    } else {
        for (let i = 1; i <= n; i++) {
            if (n % i === 0) {
                nDivide.push(i);
            }
        }
        for (let j = 1; j <= m; j++) {
            if (m % j === 0) {
                mDivide.push(j);
            }
        }
        for (let k = 1; k <= n * m; k++) {
            nMulti.push(n * k);
            mMulti.push(m * k);
        }
        for (let l = nDivide.length - 1; l >= 0; l--) {
            for (let o = mDivide.length - 1; o >= 0; o--) {
                if (nDivide[l] === mDivide[o]) {
                    nmDivide.push(nDivide[l]);
                    break;
                }
            }
        }
        answer.push(nmDivide[0]);
        for (let p = 0; p < nMulti.length; p++) {
            for (let q = 0; q < mMulti.length; q++) {
                if (nMulti[p] === mMulti[q]) {
                    nmMulti.push(nMulti[p]);
                    break;
                }
            }
        }
        answer.push(nmMulti[0]);
    }
    return answer;
}

• 하지만 제출하였을 때 테스트 케이스 11번부터 16번까지 시간초과로 실패하였고, 이를 어떻게 해결하는지 알아보기 시작하였다.
  먼저, 최소 공배수는 두 수의 곱을 최대공약수로 나눈 값이라는 것을 다시 배워 기억해내어서 적용해보았다. 그러면 중간에 최소 공배수를 구하기 위해 만들었던 배열 3개가 (nMulti, mMulti, nmMulti) 필요없고, 또한 반복문도 필요없어진다.

function solution(n, m) {
    let answer = [];
    let nDivide = [];
    let mDivide = [];
    let nmDivide = [];
    if (n < 1 || m < 1 || n > 1000000 || m > 1000000) {
        console.log('error');
    } else {
        for (let i = 1; i <= n; i++) {
            if (n % i === 0) {
                nDivide.push(i);
            }
        }
        for (let j = 1; j <= m; j++) {
            if (m % j === 0) {
                mDivide.push(j);
            }
        }

        for (let l = nDivide.length - 1; l >= 0; l--) {
            for (let o = mDivide.length - 1; o >= 0; o--) {
                if (nDivide[l] === mDivide[o]) {
                    nmDivide.push(nDivide[l]);
                    break;
                }
            }
        }
        answer.push(nmDivide[0]);
        answer.push((n * m) / nmDivide[0]);
    }
    return answer;
}

• 해당 과정을 통해 테스트 케이스를 모두 통과하고 무사히 제출하였다. 더 간단한 코드로도 이 문제를 해결할 수 있을 것이다.

최대공약수
let getGCD = (num1, num2) => {
  let gcd = 1;

  for(let i=2; i <= Math.min(num1, num2); i++){
      if(num1 % i === 0 && num2 % i === 0) gcd = i;
  }
  
  return gcd;
}

최소공배수
let getLCM = (num1, num2) =>{
  let lcm = 1;
   
  while(true){
    if((lcm % num1 == 0) && (lcm % num2 == 0)) break;
    lcm++;
  }
  return lcm
}
출처: https://velog.io/@amoeba25/JavaScript-%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98-%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0