[Java] 프로그래머스 - N개의 최소공배수

내 코드

import java.util.*;

class Solution {
    public int solution(int[] arr) {

        Arrays.sort(arr);
        int max = arr[arr.length-1];

        int gcd=1;


        while(!isCoprime(arr, max)){
            Arrays.sort(arr);
            max= arr[arr.length-1];

            for(int i=2; i<=max; i++){
                int cnt=0;
                for(int j=0; j<arr.length; j++){
                    if(arr[j]%i==0){
                        arr[j]/=i;
                        continue;
                    }
                    cnt++;
                }
                if(cnt!=arr.length){
                    gcd*=i;
                    break;
                }
            }
        }

        return gcd * Arrays.stream(arr).reduce((e1,e2)->e1*e2).getAsInt();
    }

    private boolean isCoprime(int[] arr, int max){
        for(int i=2; i<=max; i++){
            int cnt=0;
            for(int e:arr){
                if(e%i==0){
                    cnt++;
                }
            }
            if(cnt>=2){
                return false;
            }
        }
        return true;
    }
}

n개의 수가 서로소가 아닐 때까지 소인수분해를 이용해 계속 나눠나가는 방법이다.
n개의 수가 서로소일 때까지 나눈 후에는 최대공약수와 서로소들을 곱해 최소공배수를 구하는 것이다.

최소공배수 계산은 안해본지 너무 오래돼서 n개의 수의 공약수가 없을 때까지만 나눴는데, n개의 수가 서로소가 될 때까지 나누는 게 맞다고 하더라..^^
여튼 그 개념을 적용한 풀이가 되겠다.

모범 답안

class Solution {
    public int solution(int[] arr) {
        int answer = 0;

        if(arr.length == 1) return arr[0]; //원소가 한 개인 경우 바로 출력

        int g = gcd(arr[0], arr[1]); //처음 두 원소의 최대공약수
        answer = (arr[0] * arr[1]) / g; //처음 두 원소의 최소공배수

        /*  
        원소의 개수가 3개 이상인 경우
        앞의 두 원소의 최소 공배수와 다음 원소의 최소 공배수를 구하며
        배열의 끝까지 반복
        */ 
        if(arr.length > 2) { 
            for(int i = 2; i < arr.length; i++) {
                g = gcd(answer, arr[i]);
                answer = (answer * arr[i]) / g;
            }
        }

        return answer;
    }

    //최대 공약수
    private static int gcd(int a, int b) {
        int r = a % b;
        if(r == 0) return b;
        else return gcd(b, r);
    }
}

출처: https://hyojun.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-N%EA%B0%9C%EC%9D%98-%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98-Java

이 코드는 두 수의 최소공배수를 구한 뒤 이와 다음 수의 최소 공배수를 구하는 방법으로 최종 최소공배수를 구하는 방법이다.
최대공약수는 재귀로 구현해 푼 것이 인상적이었고 더 효율적인 방법이라 생각해 가져왔다 참고하자

알게된 점

stream.reduce()

• 스트림은 forEach, map메서드만 주로 사용해서 합이나 곱연산을 어떻게 할지 몰랐는데 reduce메서드로 가능하다고 하더라.
• 참고로 합의 경우 reduce도 가능하지만 sum()메서드도 지원하니 참고하자.
• 주의할 점은 reduce의 리턴타입은 OptionalXXX라는 것이다. Optional과는 달리 get()이 없고 getAsXXX형태로 값을 가져올 수 있다. 물론 orElse, orElseThrow는 공통적으로 가능하다.

예시

    OptionalInt res = Arrays.stream(arr).reduce((e1, e2) -> e1 * e2);
    res.getAsInt();