[프로그래머스][JAVA][Lv. 2] N개의 최소공배수

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/12953

---

제한 사항

---

입출력 예

---

풀이

import java.util.HashSet;
import java.util.ArrayList;
import java.util.Collections;

class Solution {
    public int solution(int[] arr) {
        ArrayList<HashSet<Integer>> numList = new ArrayList<>();
        
        for (int i = 0; i < arr.length - 1; i++) {
            numList.clear();
            
            numList.add(new HashSet<Integer>());
            for (int j = 1 ; j <= Math.sqrt(arr[i]); j++) {
                if (arr[i] % j == 0) {
                    numList.get(0).add(j);
                    numList.get(0).add(arr[i] / j);
                }
            }
            
            numList.add(new HashSet<Integer>());
            for (int j = 1 ; j <= Math.sqrt(arr[i + 1]); j++) {
                if (arr[i + 1] % j == 0) {
                    numList.get(1).add(j);
                    numList.get(1).add(arr[i + 1] / j);
                }
            }
            
            numList.get(0).retainAll(numList.get(1));
            int g = Collections.max(numList.get(0));
            arr[i + 1] = arr[i] * arr[i + 1] / g;
        }
        return arr[arr.length - 1];
    }
}

---

후기

어떤 수학적 규칙이 있는지 잘 몰라서 그냥 두 수의 최소 공배수를 구하는 방법을 반복해서 풀었다. 두 수의 곱은 최대 공약수와 최소 공배수의 곱과 같다는 것을 이용했다.