[Java] 프로그래머스 : 최대공약수와 최소공배수

1. 문제

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

코딩테스트 연습 - 최대공약수와 최소공배수

 

2. 풀이

• 최대공약수 구하기 유클리드 호제법을 활용하였다.
  • 유클리드 호제법이란?
  • 유클리드 호제법은 두 수의 최대 공약수를 구하는 알고리즘이다. ( 두 수가 서로 상대방 수를 나누어 원하는 값을 도출할 수 있는 알고리즘을 말한다.
• Math.max 와 min 메서드를 사용하여 큰 수 와 작은 수를 구하고, 작은 수가 0 이 될 때까지 반복한다.
• 임시 변수를 생성하고 작은 값을 저장한다.
• 나누어지는 값이 최대공약수로, (n * m) / a는 최소공배수가 된다.

 

3. 코드

package programmers;

import java.util.Arrays;

public class Pro_220418 {

// 도움 코드
    public static void main(String[] args) {
        int n = 2;
        int m = 5;

        System.out.println(Arrays.toString(solution(n, m)));

    }

	public static int[] solution(int n, int m) {
        int[] answer = new int[2];

        int a = Math.max(n, m);
        int b = Math.min(n, m);

        while (b > 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        answer[0] = a;
        answer[1] = (n * m) / a;

        return answer;
    }
}