빼빼로 데이 (GCD)

문제

아몬드 빼빼로를 4개, 누드 빼빼로를 8개를 구매 했다면, 다음과 같이 세 가지 방법으로 나누어 줄 수 있습니다.

• 출근한 직원이 1명이라면 아몬드 빼빼로 4개와 누드 빼빼로 8개를 줄 수 있습니다.

• 출근한 직원이 2명이라면 아몬드 빼빼로 2개와 누드 빼빼로 4개를 각각 줄 수 있습니다.

• 출근한 직원이 3명이라면 빼빼로를 남기지 않고 공평하게 주는 방법은 없습니다.

• 출근한 직원이 4명이라면 아몬드 빼빼로 1개와 누드 빼빼로 2개를 각각
  줄 수 있습니다.

팀장은 출근한 직원 수에 따라 어떻게 빼빼로를 나누어 줄지 고민하고 있습니다.

입력

인자 1: M

• Number 타입의 양의 정수 (1 ≤ M ≤ 1,000,000,000)

인자 2: N

• Number 타입의 양의 정수 (1 ≤ N ≤ 1,000,000,000)

출력

• 2차원 배열 output을 리턴해야 합니다.

• output[i]은 다음과 같은 순서를 가진 길이 3의 배열입니다.

• [빼빼로를 받게 되는 직원의 수, 나누어 주는 아몬드 빼빼로의 수, 나누어 주는 누드 빼빼로의 수]

• output은 output[i][0], 즉 '빼빼로를 받게 되는 직원의 수'를 기준으로 오름차순으로 정렬합니다.

입출력 예시

나의 코드

먼저 인자로 받은 수의 최대 공약수를 알아냅니다.

최대 공약수는 유클리드 호제법으로 구할 수 있습니다.

시간 복잡도를 고려할 수 있습니다. 최대 공약수의 제곱근 값까지 반복 순회를 수행합니다. 최대 공약수의 약수에 해당하는 수를 인자로 받은 두 개의 수에 나누는 값으로 할당합니다.

최대 공약수의 제곱근 값 까지 반복 순회를 실시하기 때문에, 제곱근 값 보다 큰 최대 공약수의 약수를 구하는 로직이 필요합니다.

iteratee의 제곱이 최대 공약수보다 작다면, 그 때 최대 공약수의 약수는 최대 공약수의 제곱근 값보다 크기 때문에, 최대 공약수에 그 iteratee 값을 나눕니다. 그 값으로 입력받은 2개의 수에 나눕니다.

결과

소스코드

function divideChocolateStick(M, N) {
  // 최대 공약수를 구하는 유클리드 호제법
  const gcd = (a, b) => (a % b === 0 ? b : gcd(b, a % b));
  const GCD = gcd(M, N);

  let result = [];
  // 시간 복잡도를 고려하여 최대 공약수의 약수를 구합니다.
  for (let i = 1; i <= Math.floor(Math.sqrt(GCD)); i++) {
    if (GCD % i === 0) {
      result.push([i, M / i, N / i]);
      // 최대 공약수의 제곱근 값이 iteratee보다 큰 경우
      // GCD에 iteratee를 나눈 값이 최대 공약수의 약수가 됩니다.
      if (i * i < GCD) {
        let j = GCD / i;
        result.push([j, M / j, N / j]);
      }
    }
  }
  // 최대 공약수의 약수를 오름차순으로 정렬합니다.
  result.sort((a, b) => a[0] - b[0]);
  return result;
}

console.log(divideChocolateStick(10, 6));