최대공약수와 최소공배수

· 문제 설명

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

 

· 제한 사항

두 수는 1이상 1000000이하의 자연수입니다.

 

· 입출력 예

n	m	return
3	12	[3, 12]
2	5	[1, 10]

 

· 입출력 예 설명

입출력 예 #1
위의 설명과 같습니다.
입출력 예 #2
자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

---

· Thinking 1

- 유클리드 호제법 : 두 수 중 큰 수와 작은 수를 정한 뒤 큰 수를 작은 수로 나누어 나머지 구하기. 나머지가 0이면 그 때의 작은 수가 최대 공약수이고, 원래의 두 수를 곱한 값을 최대 공약수로 나눈 값이 최소 공배수이다. 만약 큰 수를 작은 수로 나누었을 때 나머지가 0이 아니면 그때의 작은 수를 큰 수로 하고 나머지를 작은 수로 하여 나머지가 0이 될때까지 반복 !

 

1. 입력받은 값을 큰수와 작은수로 저장
2. 큰수 / 작은수 == 0  --> 최대공약수 : 작은 수, 최소공배수 = 큰수 * 작은수 / 최대공약수
3. 큰수 / 작은수 != 0 --> 큰수 = 작은수, 작은수 = 나머지

---

· 완성 코드

class Solution {
  public int[] solution(int n, int m) {
      int small = n > m ? m : n;
      int big = n > m ? n : m;
      int gcd = 0, lgc= 0;

      while(true) {
      	int nmg = big % small;

      	if (nmg == 0) {
      		gcd = small;
      		lgc = n * m / small;
      		break;
      	}

      	big = small;
      	small = nmg;
      }

      int[] answer = { gcd , lgc };
      return answer;
  }
}

 

---

· 문제 출처

https://programmers.co.kr/learn/courses/30/lessons/12940

알고리즘 연습 - 최대공약수와 최소공배수 | 프로그래머스