[프로그래머스] 최대공약수와 최소공배수 – 자바

---

프로그래머스 “최대공약수와 최소공배수” 문제 해결과정입니다.

최대공약수와 최소공배수

문제설명

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

제한사항

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

입출력 예

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

문제 해결과정

프로그래머스 코드

class Solution {
    public int[] solution(int n, int m) {

                int k = 0;
                // 최대공약수
		for(int i = 1; i <= Math.min(n,m); i++) if(n % i == 0 && m % i == 0) k = i;
        
                int[] result = {k, n*m/k);
 
		return result;
    }
}

최소공배수는 두 수의 곱에서 최대공약수를 나누어 준 몫과 같다. 따라서 최대공약수만 구해주면 최소공배수는 쉽게 구해진다. 1~min까지 두 수가 동시에 나누어 떨어지는 값을 최대공약수로 k에 담아준다. result에 k와 n*m/k를 담아준다.

두 줄 코드

import java.util.stream.*;

class Solution {
    public int[] solution(int n, int m) {
        int k = IntStream.rangeClosed(1, Math.min(n, m)).filter(i -> (n % i == 0) && (m % i == 0)).max().getAsInt();
        return new int[] {k,n*m/k);
    }
}

정리

1. 1~min까지 반복하여 두 수가 동시에 나누어 떨어지는 수 -> 최대공약수
2. n*m/최대공약수 -> 최소공배수이므로 result를 선언할 때 대입.

---