최대공약수, 최소공배수, 그리고 푸른 수염의 약수 개수

문제 : 프로그래머스 레벨 1 - 최대공약수와 최소공배수

문제 : 프로그래머스 레벨 1 - 기사단원의 무기

 

최대공약수

내가 두 수의 최대공약수를 구하기 위해 짰던 코드는 대략 다음과 같다. 각각의 숫자에 대해 for 반복문을 돌면서 i로 나눈 나머지가 0인 숫자들의 배열을 만들고, 두 개의 배열 중 더 짧은 배열을 기준으로 마지막 인덱스에서부터 시작해서 indexOf를 통해 최대공약수를 찾았다. 최대공약수 하나 찾기 위해서 단일 반복문이 두 개와 이중 반복문 하나를 사용한 셈이다. 당연히 성능이 좋을 리 없다.

const findGCD = (a, b) => {
  const min = Math.min(a, b);
  let gcd = 1;

  for (let i = 1; i <= min; i++) {
    if (a % i === 0 && b % i === 0) {
      gcd = i;
    }
  }

  return gcd;
}

실제로는 위와 같은 방법으로 단 하나의 반복문만으로 최대공약수를 구할 수 있다. 더 작은 숫자를 기준으로 반복문을 돌리되, a와 b 모두 나머지가 0이 되는 숫자가 공약수가 될테니까 말이다.

 

최소공배수

오래전부터 두 수의 최소공배수를 구하는 방법에는 유클리드 호제법 만한 게 없었다.

const findLCM = (a, b) => {
  const lcm = (a * b) / findGCD(a, b);
  
  return lcm;
}

 

약수의 개수

아주 당연하게도 어떤 수의 약수의 개수를 구하기 위해서 나는 처음부터 끝까지 반복문을 돌며 나머지가 0이 되는 숫자들의 개수를 세어나갔다. 이렇게 하다보니 10만이 넘어가는 숫자에 대해서 약수의 개수를 구하다가 시간초과로 끝나기 일쑤였다. 그런데 아래와 같은 방법이 있다는 사실을 알고 조금 충격을 받았다. 이 방법은 생각해보면 아주 당연한 '약수의 어떤 특성'을 활용하고 있다.

가령 18의 약수는 [1, 2, 3, 6, 9, 18]이 있다. 0번 인덱스의 약수와 arr.length-1번 인덱스를 곱하면 18이 된다. 1번 인덱스와 arr.length-2번 인덱스를 곱해도 18이 된다. 이것이 약수의 특성이라 할 수 있겠다.

function divisor(num) {
    let count = 0;

    for(let i=1; i<=Math.sqrt(num); i++) {
        if(i === Math.sqrt(num)) count += 1;
        else if(num % i == 0) count += 2;
    }
    
    return count;
}