[프로그래머스] 코테연습 - N개의 최소 공배수(lv.2)

- 내 방법 풀이

• 코드보다는 수학&논리적 사고가 필요했던 문제. (중학교 때인가, N개의 수를 각각 인수분해하여 구하는 방법이 생각난다)
• 유클리드 호재법을 사용하여 두 수의 최대공약수를 구한 뒤, 최소공배수를 구하는 방법인 (두 수의 곱)을 (두 수의 최대공약수)로 나누어 구한다.
• 앞에서부터 차례대로 최소공배수를 구하는 식으로 나간다.

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

- 다른 사람 방법 풀이

• 최소공배수, 최대공약수에 관한 알고리즘 문제의 풀이라서 비슷했던 것 같다.
• 최대 공약수 구하는 유클리드 호재법을 나와는 다르게 while문으로 짰으며, 최소공배수도 따로 클래스를 구분해주었다. 그 외 풀이는 비슷하다.

public static int solution(int[] arr) {
		      int answer = 0;
		      for(int i=0;i<arr.length;i++) {
		    	  for(int j=i+1;j<arr.length;j++) {
		    		  answer =lcm(arr[i],arr[j]);
		    	  }
		      }
		      return answer;
		  }
		 
		 static int gcd(int a, int b) {
			 while(b!=0) {
				 int r=a%b;
				 a=b;
				 b=r;
			 }
			 return a;
		 }
		 static int lcm(int a,int b) {
			 return a*b/gcd(a,b);
		 }