[Programmers] Lv. 1 최대공약수와 최소공배수

문제 설명

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

프로그래머스

 

입출력 예시

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

 

풀이 코드

Java

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        
        int multiply = n * m;
        
        if (n < m) {
            int tmp = n;
            n = m;
            m = tmp;
        }
        
        int c;
        while (m != 0) {
            c = n % m;
            
            n = m;
            m = c;
        }
        
        answer[0] = n;
        answer[1] = multiply / n;
        
        return answer;
    }
}

 

Python

def solution(n, m):
    answer = []
    
    multiple = n*m    
    
    if n < m :
        tmp = n
        n = m
        m = tmp
        
    while m != 0:
        c = n % m
        n = m
        m = c
    
    answer.append(n)
    answer.append(multiple / n)
    
    return answer

 

풀이

1. 최대공약수

유클리드 호제법 사용하기

유클리드 호제법이란?
A와 B라는 값의 최대 공약수를 구하고 싶다 가정 (단, A > B)
이때, A = B * Q + R이다.

최대 공약수를 G라고 하였을 때 아래와 같이 수식을 나타낼 수 있다. (a * G == A, b * G == B) a * G = b * G * Q + R

위 수식을 R의 입장으로 정리해보자 R = G * (a - b * Q)

즉, R도 최대 공약수 G를 약수로 갖게 되니 B와 R의 최대 공약수와 A와 B의 최대 공약수는 동일하다.

 

• 간단 정리
  • 큰 수를 작은 수로 나눈다
  • 나누는 수를 나머지로 계속 나눈다.
  • 나머지가 0이 나오면 나누는 수가 최대 공약수이다.

 

2. 최소공배수

최소공배수는 A*B / (최대공약수) 이다

 

참고 사항

Java의 배열은 원래 {}로 초기화 되어 있었지만, new int[2]로 수정하여 풀었다.

 

참고 자료
https://kangworld.tistory.com/184