GCD 최대 공약수

문제

출근한 직원에게 M, N과자를 각각 공평하게 나누어 줄 수 있는 경우의 수를 구하여라.

let M = 4;
let N = 8;
let output = divideChocolateStick(M, N);
console.log(output);
// [[1, 4, 8], [2, 2, 4], [4, 1, 2]]

answer = [직원수, M과자, N과자]

최종 풀이

function divideChocolateStick(M, N) {
  let people = [];
  let answer = [];

  let min = Math.min(M, N);

  let start = 1;
  let end = min;

// 공약수를 구한다.
  while (start < end) {
    if (!(M % start) && !(N % start)) {
      end = min / start;
      if (!(M % end) && !(N % end)) people.push(start, end);
      else people.push(start);
    }
    start += 1;
  }

// 중복 약수 제거, 순서 배치
  let sorted = [...new Set(people)].sort((a, b) => a - b);

// 직원수에 따른 경우의 수
  for (let i = 0; i < sorted.length; i++) {
    answer.push([sorted[i], M / sorted[i], N / sorted[i]]);
  }

  return answer;
}

해당 문제의 테스트케이스에는
divideChocolateStick(1000000000, 1000000000)가 있었기 때문에, 불필요한 연산을 최대한 줄일 수 있는 코드가 필요 하다.

처음 공약수를 구하는 방식은 다음과 같았다.

for(let i = 1; i < min/2; i++){
  if(!(M % i) && !(N % i)){
  	people.push(i)
  }
}

위의 코드는 연산이 500000000번 발생하여, 테스트 통과가 되지 않았다.

다시 시도한 방법은 한번 반복문을 돌 때, 나누는 수와 몫을 한번에 구하여 연산을 절반으로 줄였다.

while (start < end) {
    if (!(M % start) && !(N % start)) {
      end = min / start;
      if (!(M % end) && !(N % end)) people.push(start, end);
      else people.push(start);
    }
    start += 1;
}

=> 테스트 케이스 통과

레퍼런스

function gcd(m, n) {
  if (m % n === 0) return n;
  return gcd(n, m % n);
}

function divideChocolateStick(M, N) {
  const result = [];
  // 최대공약수를 구한다.
  // M, N의 순서는 상관없다.
  const GCD = gcd(M, N);
  let temp = 0; //

  // 약수는 대칭적이므로 제곱근까지만 반복해도 된다.
  // 예) 36의 약수는 1, 2, 3, 4, 6, 9, 12, 18, 36이다.
  // 제곱근을 기준으로 양쪽의 값 하나씩 곱했을 때 36이 되기 때문에
  // 제곱근 보다 큰 약수는 제곱근보다 작은 약수에서 구할 수 있다.
  const sqrt = Math.floor(Math.sqrt(GCD));
  for (let left = 1; left <= sqrt; left++) {
    if (GCD % left === 0) {
      // 최대공약수의 약수인 경우 중 제곱근 보다 작은 약수의 경우
      result.push([left, M / left, N / left]);
      if (left * left < GCD) {
        // 제곱근이 아닌 경우(제곱근 보다 작은)
        right = GCD / left; // 최대 공약수를 제곱근이 아닌 수로 나누면 제곱근 보다 큰 약수를 구할 수 있다.
        result.push([right, M / right, N / right]);
      }
    }
  }

  // '빼빼로를 받게 되는 직원의 수'를 기준으로 오름차순으로 정렬
  result.sort((op1, op2) => op1[0] - op2[0]);

  return result;
}

최대공약수를 구하여 접근한다. 유클리드 호제법
최대공약수를 구한 후, 1 -> 최대공약수의 제곱근까지 반복문을 돌린다.
제곱근을 기준으로 양쪽 값 하나씩 곱했을 때 최대공약수가 되므로,
제곱근 보다 큰 약수는 제곱근보다 작은 약수에서 구할 수 있다.