빼빼로 데이(최대공약수)

문제

오늘은 빼빼로 데이입니다. 한 회사의 팀장은 출근길에 아몬드 빼빼로 A 개와 누드 빼빼로 N 개를 구매하여 아침 일찍 출근길에 나섰습니다.

팀장은 자신보다 먼저 출근해있는 직원들에게 빼빼로를 모두 나누어 주려고 합니다. 단, 직원들이 서로 같은 개수의 빼빼로를 받지 못하면 시기 질투할 수 있으므로 직원들에게 같은 개수를 나누어 주어야 하며, 한 가지 종류의 빼빼로만 받는 경우가 없어야 합니다.

회사에 도착하기 전이기 때문에 이미 출근해 있는 직원들이 몇 명인지 모르는 상황입니다. 예를 들어, 팀장이 아몬드 빼빼로를 4개, 누드 빼빼로를 8개를 구매 했다면, 다음과 같이 세 가지 방법으로 나누어 줄 수 있습니다.

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

팀장은 출근한 직원 수에 따라 어떻게 빼빼로를 나누어 줄지 고민하고 있습니다. 여러분이 직원 수에 따라 빼빼로를 나누어 주는 방법을 구하는 솔루션을 제공해 주세요.

입력

인자 1: A

• Number 타입의 아몬드 빼빼로 개수

인자 2: N

• Number 타입의 누드 빼빼로 개수

출력

• 직원 수에 따라 각각 빼빼로를 나누어 주는 방법을 다음과 같은 순서로 배열에 담아야 합니다.
  • Number 타입의 요소
  • [빼빼로를 받게 되는 직원의 수, 나누어 주는 아몬드 빼빼로의 수, 나누어 주는 누드 빼빼로의 수]
• 위와 같은 방법들을 순서에 상관없이 배열에 담아 출력해야 합니다.

주의사항

• 1 ≤ A, N ≤ 1,000,000,000 (A는 구매한 아몬드 빼빼로 개수, N은 구매한 누드 빼빼로 개수 )
• TIP : 위 범위와 가까운 최대 공약수인 경우, 모든 최대 공약수의 약수를 탐색하는 것은 비효율적 입니다. 제곱근을 활용할 수 있어야 합니다.
  • 36의 약수는 1, 2, 3, 4, 6, 9, 12, 18, 36 입니다. 36의 제곱근 6을 기준으로 이하 약수를 통해 모든 약수를 구할 수 있습니다.
  • 1 x 36 = 2 x 18 = 3 x 12 = 4 x 9 = 6 x 6 = 36 입니다.

입출력 예시

let A = 4;
let N = 8;

let output = divideChocolateStick(A, N);
console.log(output) 
// [[1, 4, 8], [4, 1, 2], [2, 2, 4]] 또는,
// [[1, 4, 8], [2, 2, 4], [4, 1, 2]] 
// 순서는 상관없습니다

// 최대 공약수(유클리드 호제법: Euclidean algorithm)
function gcd(A, N) {
     return (A % N) === 0 ? N : gcd(N, A % N); 
}

function divideChocolateStick(A, N) {
    const result = [];
    let value = 0; // 최대공약수를 담을 변수
    let temp = 0; //

    if(A > N) value = gcd(A, N); // A가 N보다 큰 경우
    else value = gcd(N, A); // N이 A보다 큰 경우

    // 제곱근 까지만 반복해도 된다.
    // 최대 공약수가 36이라면 36의 약수는 1, 2, 3, 4, 6, 9, 12, 18, 36이다.
    // 이는 1 * 36 = 2 * 18 = 3 * 12 = 4 * 9 = 6 * 6 이다.
    // 즉, 제곱근을 기준으로 양쪽의 값 하나씩 곱했을 때 36이 되기 때문에
    // 제곱근 보다 큰 약수는 이미 제곱근보다 작은 약수에서 구할 수 있다.
    // 따라서 제곱근까지만 비교해 주면 된다.
    for(let i = 1; i * i <= value; i++) {
        if(value % i === 0) { // 최대공약수의 약수인 경우 중 제곱근 보다 작은 약수의 경우
            result.push([i, A / i, N / i]);
            if(i !== value / i) { // 제곱근이 아닌 경우(제곱근 보다 작은)
                temp = value / i; // 최대 공약수를 제곱근이 아닌 수로 나누면 제곱근 보다 큰 약수를 구할 수 있다.
                result.push([temp, A / temp, N / temp]);
            }
        }
    }
    
    return result;
}