[28번][중급] 최대공약수와 최소공배수

프로그래머스

 

 

나의 답

[pseudo code]
최소공배수 = Math.abs(a*b)/최대공약수
최대공약수 = n의 약수 중 m의 약수와 같은 최대 값

약수

let sqrt = Math.sqrt(n);
    for (let i = 1; i <= sqrt; i++) {
        if (n % i === 0 && i !== sqrt) {
            i & n / i;
        } else if (i === sqrt) {
            i;
    }

1. 최대공약수 변수 gcd를 선언, 0으로 초기화
2. d & m의 약수를 받을 변수 dN과 dM을 선언, makeDivisor()로 초기화 (hoisting & !TDZ)
3. 약수를 만들어 줄 makeDivisor() 함수를 생성
    - 함수 안에서 약수를 받아 줄 빈 배열을 생성
    - 1 ~ num까지 1씩 증가시키면서 num을 나눠준 값이 0이면 약수이므로, i를 배열에 넣어주고
    - loop가 끝난 뒤 약수 배열을 반환
4. gcd 값 받아오기 (dN과 dM의 배열의 큰 값 > 작은값 순으로 검사)
    - gcd <=0인 동안, while 문을 돌면서:
        - 만약, dM의 최대값이 dN의 최대값보다 작으면, dM의 최대값이 dN 배열에 있는지 확인 후, 있다면 gcd 값으로, 없으면 dM.pop()으로 다음 값을 검사
        - dN의 최대값이 더 작은 경우, 위와 같은 로직으로 처리
5. 최소공배수 변수 lcm = Math.abs(n*m)/gcd
6. return [lcm, gcd]

 

function solution(n, m) {
  let gcd = 0; // greatest common divisor
  let dN = makeDivisor(n),
    dM = makeDivisor(m);

  function makeDivisor(num) {
    let arr = [];
    for (let i = 1; i <= num; i++) {
      if (num % i === 0) arr.push(i);
    }
    return arr;
  }

  while (gcd <= 0) {
    let i = dM[dM.length - 1],
      j = dN[dN.length - 1];
    i <= j
      ? dN.includes(i)
        ? (gcd = i)
        : dM.pop()
      : dM.includes(j)
      ? (gcd = j)
      : dN.pop();
  }

  let lcm = Math.abs(n * m) / gcd; // least common multiple
  return [gcd, lcm];
}

console.log(solution(3, 12));
console.log(solution(2, 5));

 

 

 

인상적인 다른 사람의 답

일단, n%m == 0이면, n이 m의 약수임을 이용해서 엄청 간결하게 알고리즘을 짰음
for loop의 조건문에 일반적인 조건 대신 r = a%b를 사용하였음

 

for literal : for (initialization; condition; afterthought) statement
condition
 An expression to be evaluated before each loop iteration. If this expression evaluates to true, statement is executed. If the expression evaluates to false, execution exits the loop and goes to the first statement after the for construct.
-MDN for

function gcdlcm(a, b) {
  var r;

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

console.log(gcdlcm(3, 13));

/*
이해를 돕기 위해 r, a, b 값을 찍어 봄
r: 3 a 3 b 13
r: 1 a 13 b 3
r: 0 a 3 b 1
[ 1, 39 ]

*/