프로그래머스 최대공약수와 최소공배수(Java)

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

문제명 : 최대공약수와 최소공배수

언어 : 자바(Java) 

 

일단 최대공약수란?

두 수를 나눴을 때 (3, 12라 가정)

두 수를 같은 수로 나누었을 때 나머지가 0인 값 중에 가장 큰 수!!

 

그 다음으로 최소공배수란? 두 수를 계속 같은 수로 곱하다가

두 숫자의 값이 같아지는 경우!!

(2와 5를 서로 *2*2*2 *5*5*5 이런 식으로 하다가 보면 10에서 같아짐)

 

그냥 정직하게 풀면 효율성에서 걸려서 유클리드 호제법을 사용해야 하는데

두 수를 곱한 뒤 최대공약수로 나누면 최소공배수를 구할 수 있다

 

즉 최대공약수를 먼저 구한 뒤 최소공배수를 구하면 된다는 것이다

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

 

먼저 받은 두 값 중에서

큰 값을 먼저 구한 뒤에

 

큰 값을 가지고 최대공약수를 구하는데

큰 값에서 1씩 줄여보면서 두 값을 가지고 나눴을 때 0으로 나눠 떨어진다면

그게 바로 최대공약수!

 

최대공약수를 구한 순간

바로 유클리드 호제법을 사용해서

두 수를 곱한 뒤에 최대공약수로 나누면 최소공배수가 되므로

최대공약수를 answer 0번에

최소공배수를 answer 1번에 반환하면 끝이 난다

 

마지막으로 프로그래머스에 바로 적용 가능한 답안은 아래와 같다

 

class Solution {
  public int[] solution(int n, int m) {
	      int[] answer = new int[2];
	      int largeVal = 0;
	      
	      // 큰 수 찾기
	      if(n < m) {
	    	  largeVal = m;
	      } else {
	    	  largeVal = n;
	      }
	      
	      // 최대공약수 구하기
	      int i = largeVal;
	      while(1 < largeVal) {
	    	  if (n % i == 0 && m % i == 0) {
	    		  // 유클리드 호제법 : 두 수를 곱한 뒤 최대공약수로 나누면 최소공배수
	    		  answer[0] = i;
	    		  answer[1] = n * m / i;
	    		  break;
	    	  }
	    	  i = i -1;
	      }
	      
	      return answer;
  }
}