최소공배수 구하기

코테를 풀어보기 시작했다!
최소공배수 구하기를 수학 문제 푸는거로는 너무 쉽게 했었는데 이렇게 코드로 짜려니까 너무너무 어려웠다...

내가 우선 문제를 읽고 생각한 내용들
- list : 672 672 672 672 224 224 224 168 168 168 168 96 96 96
- 672와 168만 최소공배수의 후보가 될 수 있다
- list에서 4개씩 있는 숫자를 뽑고 (count로 개수를 세자 ! )
- 그 수들 중에 작은 수를 고르면 되지 않을까??

첫 번째 코드 !실패!

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class LeastCommonMultiple {
    public static int solution(int[] arr) { 
        int answer = 0;
        int mul = 1;
        int num[] = new int[arr.length + 1];
        ArrayList<Integer> list = new ArrayList<>(); // 최소공배수 후보를 담은 array

        Arrays.sort(arr);

        // 다 곱한거 : 1728
        for(int i = 0; i < arr.length; i++){
            mul = mul * arr[i];
        }

        for(int i = 0; i < arr.length - 1; i++){
            num[i] = mul / arr[i]; // 576, 432, 192, 108
            list.add(num[i]);

            for(int j = 0; j < arr.length; j++) {

                if (num[i] % arr[j] == 0) {
                        continue;
                } else {
                    System.out.println("펑 : " + list.remove(num[i]));
                    list.remove(num[i]);
                }
            }
        }

        System.out.println(list);

        // 최소 공배수 후보를 담은 배열에서의 최소값이 정답
        answer = Collections.min(list);

        return answer;
    }

}

→ 반례가 될만한 예시가 있나 찾아보았더니 주어진 숫자가 [3,4,9,16] 일 경우 위의 알고리즘에 적용해 보았을 때의 답은 192가 된다. 하지만 실제 최소공배수는 144가 정답이다. 따라서 다른 답이 나오므로 테스트 케이스에서는 답이 잘 나왔지만 예외의 경우가 있었다..! 그래서 저런 예외적인 상황에 대한 코드를 추가해야할 것 같다ㅜㅜㅜ!

정답 코드

public class LeastCommonMultiple {
    public static int Max(int a, int b){
        // 최대공약수 구하는 함수
        int max = 0;
        int compare;

        if(a > b){
            compare = b;
        }else{
            compare = a;
        }

        // 둘 중 작은 수까지만 for문을 돌린다.
        // 어차피 약수를 구하는 거니까 많이 돌릴 필요 x
        // 0으로 나누면 오류가 뜨기 때문에 i는 1부터 시작
        for(int i = 1; i <= compare; i++){
            if(a % i == 0 && b % i == 0){
                max = i;
                // 두 수 모두 나누어 떨어지게 만드는 i 가 최대공약수
            }
        }
        return max;
    }

    public static int Min(int a, int b){
        // 최소공배수 구하는 함수
        // 두 수의 곱을 두 수의 최대공약수로 나눠준다.
        int min = (a * b) / Max(a, b);
        return min;
    }

    public static int solution(int[] arr) { // 3,4,9,16
        // for 문 내에서 처음 최소공배수를 구할 때 들어갈 숫자이므로 arr[0]으로 초기화한다.
        int answer = arr[0];

        for(int i = 1; i < arr.length; i++){
            // 두 수의 최소공배수를 구한다.
            // 그렇게 구해진 최소공배수와 그 다음 수와의 최소공배수를 구한다
            answer = Min(answer, arr[i]);
        }

        return answer;
    }

}