[알고리즘] GCD를 이용하여 과자를 공평하게 분배하기

문제 조건

- 아몬드 빼빼로 M개와 누드 빼빼로 N개를 모든 직원들에게 공평하게 나누어주기

- 각 직원들은 종류별로 똑같은 수의 빼빼로를 받아야 함 

- 직원 수에 따라 빼빼로를 나누어 주는 솔루션 구하기

 

전달 인자와 출력값

- 전달인자1 : number 타입의 양의 정수 M (1 ≤ M ≤ 1,000,000,000)

- 전달인자2 : number 타입의 양의 정수 N (1 ≤ N ≤ 1,000,000,000)

- 출력값 : 2차원 배열 리턴

- 출력값의 엘리먼트 : [빼빼로를 받는 직원 수, 나누어 주는 아몬드 빼빼로의 수, 나누어 주는 누드 빼빼로의 수]

 

코드 작성 포인트

1. 빼빼로를 받는 직원의 수 : 최대공약수의 약수

2. 나누어 주는 빼빼로의 수 : M/(직원 수), N/(직원 수)

3. 최대공약수(GCD) : 유클리드 호제법으로 구하기

4. GCD의 약수 구하기 : 제곱근까지만 반복문으로 구하고, 그 이상의 약수는 GCD에서 나누어줘서 구하기

 

코드 작성하기

약수는 대칭적이므로 제곱근까지만 반복 (ex. 36의 약수 : 1, 2, 3, 4, 6, 9, 12, 18, 36)

제곱근을 기준으로 양쪽의 값 하나씩 곱했을 때 해당 숫자가 나옴

(제곱근 보다 큰 약수) = (해당 숫자) / (제곱근보다 작은 약수)

 

// 최대 공약수 구하는 함수 구현(유클리드 호제법: Euclidean algorithm)
function gcd(m, n) {
  if (m % n === 0) return n;
  return gcd(n, m % n);
}

function divideChocolateStick(M, N) {
  
  const result = [];      // 리턴할 2차원 배열
  const GCD = gcd(M, N);  // 최대공약수
  let temp = 0; //

  // 시간복잡도를 줄이기 위해 반복문은 제곱근까지만 돌리기
  // (제곱근보다 큰 약수) = GCD / (제곱근보다 작은 약수)
  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;
}