[Java] 알고리즘, "최대공약수와 최소공배수"

최대공약수, 최소공배수를 구하라

문제 설명

두 수를 입력받습니다. 두 수의 최대공약수, 최소공배수를 반환하는 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]을 리턴해야 합니다.

나의 풀이

class Solution {
  public int[] solution(int n, int m) {
      int[] answer = new int[2];
      //두수의 크기 정렬
      int big,small;
      if(n>m){
          big = n; small = m;
      }else{
          big = m; small = n;
      }
      answer[0] = gcd(big,small);
      answer[1] = big*small/answer[0];
      
      return answer;
  }
  public int gcd(int a,int b){
      if(a % b == 0)
          return b;
      return gcd(b,a%b);
  }
}

저는 일단 임의의 gcd 메소드를 만들어 두 수를 넣으면 최대공약수를 리턴하는 메소드를 만들었고, 최소공배수는 이렇게 구해진 최대공약수를 이용하는 흐름으로 해결하였습니다. 대부분의 알고리즘이 유클리드의 호제법을 이용하여 대중적으로 널리 알려진 알고리즘이었고, 제가 그냥 통째로 저 알고리즘을 외워놨었기 때문에 거의 암기식으로 쉽게 풀 수 있었던 문제였습니다. 유클리드의 호제법은 네이버 지식백과에 자세한 설명으로 나와있으니 참조해보시길 바랍니다. 참고로 이런 공식 구하는데 들어가는 알고리즘은 대부분 대중적으로 구현된 모델 1개정도는 외워놓는 편이 좋다고 생각합니다. ^^

다른사람의 풀이

import java.util.Arrays;
 
class TryHelloWorld {
    public int[] gcdlcm(int a, int b) {
      int[] answer = new int[2];
      int temp=1;
      int gcd=a*b;
      while(temp!=0){
        temp=b%a;
        b=a;
        a=temp;
      }
      answer[0]=b;
      answer[1]=gcd/b;
        return answer;
    }
 
    // 아래는 테스트로 출력해 보기 위한 코드입니다.
    public static void main(String[] args) {
        TryHelloWorld c = new TryHelloWorld();
        System.out.println(Arrays.toString(c.gcdlcm(3, 12)));
    }
}

이 분도 전체적인 원리는 유클리드의 호제법을 이용해서 푸신 것 같습니다. temp를 이용해서 while 조건변수로 이용하는 것과 저처럼 재귀함수 호출을 이용하여 반복하는 방법중에 전자를 택하신 것같아요. 어느방법이든 원리는 같으므로 대부분의 최대공약수, 최소공배수를 구하는 알고리즘은 유클리드 호제법을 이용해서 접근해야 하는 것 같습니다. 외워두면 더 좋구요^^