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

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

프로그래머스

문제 분류 : 코딩테스트 연습 > 연습문제 > N개의 최소공배수

난이도 : 2

 

문제 접근 1 (브루트 포스)

1부터 ~ 정답까지 

class Solution {
    public int solution(int[] arr) {
        int answer = 1;
        while(true){
            boolean flag = true;
            for(int target : arr){
                if(answer % target !=0){
                    flag = false;
                    break;
                }
            }
            if(flag) break;
            answer++;
        }
        return answer;
    }
}

 arr의 길이도 최대 15이고 arr의 원소가 100이하여서 시간초과는 발생하지 않는다.

문제 접근 2 (GCD, LCM 활용)

GCD : 최대 공약수

LCM : 최소 공배수 

A와 B가 있다. 

A * B = GCD * LCM 이라는 공식이 있다. 

GCD (최대 공약수는 재귀를 통해서 쉽게 구할 수 있다.)

 public static int GCD(int a, int b){
        if(b == 0) return a;
        return GCD(b, a % b);
 }

 

1. A와 B 사이에서 GCD를 구한다.

2. A * B = GCD * LCM 이라는 공식을 이용해서 LCM 을 구한다. LCM = A * B / GCD 

3. A를 LCM으로 갱신하고 다음 인덱스로 진행 

4. 1번 2번 3번을 반복 

class Solution {
    public int solution(int[] arr) {
         int start = arr[0];
         for(int i = 1; i < arr.length; i++){
             int target = arr[i];
             start = (start * target) / GCD(start, target); 
         }
         return start;
    }
    public static int GCD(int a, int b){
        if(b == 0) return a;
        return GCD(b, a % b);
    }
}

테스트 케이스 6은 엄청난 차이를 보인다.

이 문제는 입력 범위가 작아서 접근 1번으로도 통과 하지만 입력값이 조금만 커져도 접근 1번으로는 통과 못한다.