프로그래머스 문제풀이(N개의 최소공배수) with JAVA

mikseoo·2020년 4월 7일

Java 알고리즘 코딩테스트 프로그래머스

오랫만에 풀어보는 코딩테스트 문제이다. 요새 학교 공부랑 날이 좋아서 내 공부를 따로 많이 못했다(핑계;).

문제 설명

숫자 배열이 주어지면 그 숫자들의 공통된 최소공배수를 구하는 문제이다.

문제 풀이 방법

최대공약수와 최소공배수 구하는 방법을 알아낸다.
따로 최대공약수, 최소공배수 구하는 클래스를 생성한다.
메인 클래스에서 관계에 따라서 알고리즘을 구현한다.

최대공약수 알고리즘

최대공약수란?

먼저 공약수란, 이름에서 알 수 있듯이 두 수, 혹은 그 이상의 여러 수의 공통인 약수라는 뜻이다. 최대공약수는 당연히 공약수 중 가장 큰 것. 두 수 a,b의 최대공약수를 수학적 기호로 표시하면, gcd(a,b)이며,더욱 줄여서 (a,b)로 표기하기도 한다.특히, gcd(a,b)=1이면 두 수 a,b는 서로소(relatively prime, coprime)라고 한다.

유클리드 호제법

알고리즘 문제에서 최대공약수 관련 문제는 보통 유클리드 호제법이라는 것을 사용한다.

유클리드 호제법이란?

static int gcd(int a, int b) {
			 while(b!=0) {
				 int r=a%b;
				 a=b;
				 b=r;
			 }
			 return a;
		 }

이와 같이 두수가 있으면 처음에 그 중 한 수(여기서는 b)로 나누고 나머지를 임시 변수(r)에 저장하고 나누어진수(a)는 나눈수(b)가 되고 나눈수(b)는 임시변수(r)이 된다. 그리고 b가 0이 아닐때 까지 반복하다 0이 되면 a를 return 하게 되는데 a가 a,b의 최대공약수가 된다.

최소공배수란?

공배수란, 이름에서 알 수 있듯이 두 수, 혹은 그 이상의 수들의 공통인 배수라는 뜻이다. 최소공배수는 당연히 공배수 중에서 가장 작은 것. 두 수 a,b의 최소공배수를 기호로 lcm(a,b)로 표기하며, 더욱 줄이면 [a,b]로 표기하기도 한다.

최소공배수 구하는법

간단하다 , 이것 또한 알고리즘 문제에서 가장 많이 쓰이는 식인데
최소공배수 = 두수의 곱 / 두수의 최대공약수

나의 풀이 코드

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;
		  }
		 
		 public static void main(String[] args) {
			 int[] arr = {8,2,14,6};
			System.out.print(solution(arr));
		 }
		 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);
		 }

최대공약수 클래스를 gcd로 생성하고 최소공배수 클래스를 lcm으로 생성 하였다.
solution 클래스에서 배열을 받아와서 차례대로 모든 수의 최소공배수를 구하고 싶어서 변수를 i,j두개를 생성해서 반복문을 돌렸지만 ,,,

실행 결과

마지막 두 수의 최소공배수만 구해지게 되었다.

해결 방법

굳이 변수두개로 해서 모두 돌릴 필요없이 전체 배열의 최소공배수 이기 때문에 하나를 기준으로 잡고 나머지 데이터와 최소공배수를 차례대로 구하는 방식을 사용했다.

public static int solution(int[] arr) {
		      int answer = 0;
		      int lcm1 = arr[0];
		      for(int i=0;i<arr.length;i++) {
		    	  
		    		  lcm1 =lcm(lcm1,arr[i]);
		    	  
		      }
		      return lcm1;
		  }