JAVA 알고리즘 - 최대공약수와 최소공배수

문제 설명

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요.

배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다.

예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.


제한 사항

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


문제풀이

최소공배수와 최대공약수를 구하는 방법은 아래 N개의 최소공배수 구하기 글에서 설명했었습니다.

JAVA 알고리즘 - N개의 최소공배수 구하기


다시한번 리마인드 하자면, A*B / 최대공약수 -> 두 수의 최소공배수를 구하는 알고리즘이고,

최대공약수는 나머지가 0이 아닐때 까지 while 문을 통해 두 수를 나누어 리턴되는 값으로 두 수의 최대공약수를 구할 수 있습니다.

이 알고리즘을 이해하면 문제를 쉽게 접근할 수 있습니다!

  1. class Solution {
  2. public int[] solution(int n, int m) {
  3. int[] answer = {};
  4. answer = new int[2];
  5. answer[0] = gcd(n,m);
  6. answer[1] = lcm(n,m);
  7. return answer;
  8. }
  9. // 최소공배수 lcm(a*b / 최대공약수)
  10. static int lcm ( int n, int m ){
  11. return n*m / gcd(n, m);
  12. }
  13. // 최대공약수 gcd(a, b)
  14. static int gcd(int n, int m){
  15. while ( m != 0){
  16. int t = n%m;
  17. n = m;
  18. m = t;
  19. }
  20. return n;
  21. }
  22. }



* 파트너스 활동을 통해 일정액의 수수료를 제공받을 수 있음
작성자 소개
최찬희 프로필
WrapUp 블로거

최찬희

반려견을 좋아하고, 차를 좋아하고, 여행을 좋아하고, 맛집을 찾아 즐기는 웹 개발자 입니다^^

댓글작성

작성자의 다른 포스팅