최대공약수와 최소공배수

문제

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요.
배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다.
예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

제한 사항

• 두 수는 1이상 1000000이하의 자연수입니다.

입출력 예

n	m	return
3	12	[3, 12]
2	5	[1, 10]

정답

function solution(n, m) {
    let min = 1;
    let max = m;

    while(true) {
        if (max % m === 0 && max % n === 0) {
            break;
        }
        max++;
    }

    for (let i = 2; i <= n; i++) {
        if (n % i === 0 && m % i === 0) {
            min = i;
        }
    }

    return [min, max];
}

풀이

2번의 반복문을 사용하였습니다.

while문에서는 최소공배수를 구하기 위해 큰 수인 m부터 반복문을 돌며
n과 m으로 각각 max를 나누었을 때 모두 나머지가 0인지 판별하고 0이라면 멈추게됩니다.

이후 최대공약수를 구하기위해 for문을 통해 약수에 해당하는 2부터 1씩 증가하며
마찬가지로 n과 m을 나누었을 때 모두 나머지가 0인지 확인합니다.
n까지 반복하며 가장 마지막에 min값에 할당되는 i가 최대공약수입니다.

리팩토링

유클리드 호제법을 이용한 재귀함수로 최대공약수를 구하고
이후 (a * b) / 최대공약수를 통해 최소공배수를 구합니다.

• 유클리드 호제법이란?
  2개의 자연수 a, b가 주어졌을 때 a % b의 나머지인 c가 0이 아닐 경우
  b % c를 연산하며 나머지가 0이 나올 때 까지 반복한다.
  이 후 나머지가 0일 때 b의 자리에 위치한 수가 최대공약수가 된다.
  Ex. a = 72, b = 30

a	b	나머지
72	30	12
30	12	6
12	6 (최대공약수)	0

function solution(a, b) {
    const min = dcg(a, b);
    const max = (a * b) / min;
    return [min, max];
}

function dcg(a, b) {
    const division = a % b;

    if (division === 0) {
        return b;
    };

    return dcg(b, division);
}

성능 개선

	초기답안	리팩토링 답안
테스트 1	(0.09ms, 30.2MB)	(0.04ms, 30.1MB)
테스트 2	(0.08ms, 30.3MB)	(0.05ms, 30.1MB)
테스트 3	(0.06ms, 30.1MB)	(0.10ms, 29.8MB)
테스트 4	(0.07ms, 30MB)	(0.04ms, 30.1MB)
테스트 5	(0.10ms, 29.9MB)	(0.05ms, 30.2MB)
테스트 6	(0.05ms, 29.9MB)	(0.04ms, 30.2MB)
테스트 7	(0.05ms, 30.2MB)	(0.09ms, 30.1MB)
테스트 8	(0.06ms, 30.3MB)	(0.04ms, 30.2MB)
테스트 9	(0.22ms, 30.2MB)	(0.07ms, 29.9MB)
테스트 10	(0.08ms, 30.3MB	(0.04ms, 29.9MB)
테스트 11	(3.67ms, 32.7MB	(0.10ms, 30.2MB)
테스트 12	(7.20ms, 32.7MB	(0.08ms, 30MB)
테스트 13	(3.91ms, 32.8MB	(0.05ms, 30.2MB)
테스트 14	(7.47ms, 32.8MB	(0.07ms, 29.9MB)
테스트 15	(0.24ms, 30MB)	(0.04ms, 30.2MB)
테스트 16	(5.00ms, 32.8MB	(0.04ms, 29.9MB)