[프로그래머스] 최대공약수와 최소공배수 - JavaScript

javascript

문제 설명

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

제한 조건

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

예시

입출력 예

n    m        return

3    12        [3, 12]
2    5        [1, 10]

설명
입출력 예 #1
위의 설명과 같습니다.

입출력 예 #2
자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

---

내가 작성한 코드

function solution(n, m) {
    const [num1, num2] = [n, m].sort((x, y) => x - y)
    let min = num2; // 최소공배수
    // num1 * num2 / min = 최대공약수

   while(true) {
       if ((min % num1 === 0) && (min % num2 === 0)) {
           break;
       }
       min++;
   }
   return [num1 * num2 / min, min];
}

우선 최소공배수를 구한 후, 최대공약수를 구하면 된다.
-> 최대공약수는 두 수의 곱 / 최소공배수 이므로 최소공배수를 먼저 구한다.

최소공배수는 두 수의 배수이면서 (= 두 수 모두 최소공배수의 약수여야 한다) 최소인 수이므로,
두 수중 큰 수부터 시작해서 +1씩 늘려가면 된다.

실행 결과

테스트 1 〉    통과 (0.08ms, 30.2MB)
테스트 2 〉    통과 (0.10ms, 30.1MB)
테스트 3 〉    통과 (0.08ms, 30.1MB)
테스트 4 〉    통과 (0.12ms, 29.9MB)
테스트 5 〉    통과 (0.09ms, 30.1MB)
테스트 6 〉    통과 (0.07ms, 30MB)
테스트 7 〉    통과 (0.07ms, 30MB)
테스트 8 〉    통과 (0.13ms, 30.1MB)
테스트 9 〉    통과 (0.09ms, 29.9MB)
테스트 10 〉    통과 (0.08ms, 29.9MB)
테스트 11 〉    통과 (3.04ms, 32.6MB)
테스트 12 〉    통과 (5.10ms, 32.3MB)
테스트 13 〉    통과 (3.71ms, 32.5MB)
테스트 14 〉    통과 (5.51ms, 32.6MB)
테스트 15 〉    통과 (0.19ms, 30.1MB)
테스트 16 〉    통과 (4.66ms, 32.6MB)

---

리팩토링

function solution(n, m) {
    let min = 1;
    for (let i=1; i<=n*m; i++) {
        if ((i % n === 0) && (i % m === 0)) {
            min = i;
           break;
       }
    }
   return [n*m/min, min];
}

최소공배수의 최대값은 n*m이 되니 for문을 이용할 수 있다.
오름차순 sort를 해서 큰 값을 찾는 과정은 생략하고, min의 최소값은 1로 하여 반복문을 실행한다.

실행 결과

테스트 1 〉    통과 (0.05ms, 30.2MB)
테스트 2 〉    통과 (0.09ms, 30MB)
테스트 3 〉    통과 (0.06ms, 30.1MB)
테스트 4 〉    통과 (0.06ms, 30.1MB)
테스트 5 〉    통과 (0.04ms, 29.8MB)
테스트 6 〉    통과 (0.05ms, 29.8MB)
테스트 7 〉    통과 (0.05ms, 30.2MB)
테스트 8 〉    통과 (0.04ms, 30.2MB)
테스트 9 〉    통과 (0.05ms, 30.2MB)
테스트 10 〉    통과 (0.05ms, 29.8MB)
테스트 11 〉    통과 (3.10ms, 32.6MB)
테스트 12 〉    통과 (5.24ms, 32.6MB)
테스트 13 〉    통과 (3.84ms, 32.7MB)
테스트 14 〉    통과 (5.29ms, 32.7MB)
테스트 15 〉    통과 (0.27ms, 30.1MB)
테스트 16 〉    통과 (5.41ms, 32.6MB)

만약 n,m이 커지면 i=1부터 시작하는 것이 성능이 좋지 않은 듯 하다. (✅sort를 추가해봤으나 큰 차이 없음을 확인)
하지만 테스트 1-10까지는 성능이 훨씬 좋아졌다.