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

사이트명 : 프로그래머스(Programmers)

문제명 : N개의 최소공배수

언어 : 자바(Java)

 

여러 숫자를 배열로 받은 뒤 이 숫자의 최소공배수를 찾는 문젠데

그냥 정직하게 찾으면 효율성에 걸린다

 

그래서 유클리드 호제법을 사용해야 하는데

유클리드 호제법이란?

두 수를 곱한 뒤 이 수들의 최대공약수로 나눠보면 최소공배수를 구할 수 있다

 

내 풀이방법은 아래와 같은데

 

먼저 큰 수를 찾은 뒤 큰 수에서 1씩 줄여보면서 최대공약수를 찾는다

이후 배열의 두 수를 곱해서 최대공약수로 나누는 유클리드 호제법을 진행하면서

다음 배열에는 두 수의 최소공배수를 넣는다

 

유클리드 호제법으로 돌리고 돌려서

각 수들의 최소공배수를 계속 구하면

결국 배열에 주어진 값들의 최소공배수를 구할 수 있다

 

다른 방법으로도 풀 수는 있는데

효율성을 통과를 못하기 때문에 유클리드 호제법을 무조건 사용해야 하는 것 같다

 

마지막으로 프로그래머스에 바로 적용 가능한 코드는 아래와 같다

 

class Solution {
  public int solution(int[] arr) {
      int answer = 0;
      int largeVal = 0;
      int smallVal = 0;
      
      for(int i = 0; i<arr.length; i++) {
    	  
		  if(i == arr.length-1) {
			  answer = arr[i];
			  return answer;
		  }    	  
    	  
		  if(arr[i] > arr[i+1]) { // 큰 수 찾기
			  largeVal = arr[i]; 
			  smallVal = arr[i+1];
		  } else {
			  largeVal = arr[i+1]; 
			  smallVal = arr[i];    			  
		  }
		  
		  for(int j = largeVal; j>0; j--) {
			  if(largeVal % j == 0 && smallVal % j == 0) {
				  arr[i+1] = (arr[i] * arr[i+1]) / j;
				  arr[i] = 0;
				  
				  break;
			  }
		  }
    	  
      }
      
      return answer;
  }
}