✏️ 문제 설명

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

✏️ 제한 사항

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

✏️ 문제 풀이

📍 첫번째 시도 - 성공

최소공배수를 먼저 구해서 최소공배수를 이용해 최대공약수를 구하는 방식으로 문제를 해결했다.

컴파일러에게 노가다를 시키는 방법도 있지만 최소한의 연산으로 효율적으로 문제를 해결하기 위해 수학 지식을 검색해 찾아봤다.

• 최대공배수 = 두 수의 곱 ÷ 최소공배수

import java.util.*;

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        
        // 최소공배수를 체크하기 위해서 배수를 Map 에 저장했다.
        Map<Integer, Integer> lcm = new HashMap<>();

        // 문제를 해결하기 위한 for 문
        // 공배수가 몇번째에 나올지 알 수 없기 때문에
        // 무한 루프가 돌 수 있게 만들었고.
        // 배수를 찾게되면 break 로 탈출할 수 있게 만들었다.
        for (int i = 1; true; i++) {
            if (lcm.get(n * i) == null) lcm.put(n * i, 0);
            else {
                // 공배수를 찾게되면 answer 에 값을 채워주게 된다.
                answer[1] = n * i;
                // 공배수의 값을 이용해 최대공약수를 구해준다.
                answer[0] = (n * m) / answer[1];
                break;
            }

            if (lcm.get(m * i) == null) lcm.put(m * i, 0);
            else {
                answer[1] = m * i;
                answer[0] = (n * m) / answer[1];
                break;
            }
        }
        return answer;
    }
}

📍 다른사람의 풀이

내가 찾아낸 공식 최대공배수 = 두 수의 곱 ÷ 최소공배수 공식을

거꾸로 최소공배수 = 두 수의 곱 ÷ 최대공배수 이렇게 만들어

공배수 먼저 구한 뒤 공약수를 구하는 방법으로 문제를 해결했다.

이 풀이를 보고 수학의 가능성에 정말 놀랐다.

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];

        for (int i = 1; i < n + m; i++) {
            if (n % i == 0 && m % i == 0) {
                answer[0] = i;
                answer[1] = n * m / answer[0];
            }
        }
        return answer;
    }

}

✏️ 풀이에 도움된 수학 공식

🔗 최대공약수 구하는 방법

🔗 최소공배수란?