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

 

문제 설명

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

 

나의 풀이

최대공약수 : 두 자연수의 공통된 약수 중 가장 큰 수 

최소공배수: 두 자연수의 공통된 배수 중 가장 작은 수 

 

최대공약수를 구하기 위해 우선 Math.min을 통해서 두 수 중 작은 값을 구하고, 

거기서 for문을 돌려서 n, m 수 로 나눠떨어지는 값을 구한다. 

 

그리고 그 값이 최대공약수가 되고, 최소공배수는 주어진 두 수를 곱하고 최대공약수를 나누면 구할 수 있다.

 

 

다른 사람 풀이  

재귀함수로 최대공약수랑 최소공배수를 구한 풀이이다. 

gcd 함수로 최대공약수를 구하고 거기서 구한 값을 (a * b)에 나누면 최소공배수를 구할 수 있다. 

 

gcd 메서드를 보면 p와 q의 수가 주어졌다고 할 때 

p % q 가 0이면 최대 공약수에 해당되기 때문에 return p를 해주고, 

아니면 계속 반복하면서 최대공약수를 구한다. 

 

2개의 자연수  a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면 (단 a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r0를 구하고, 다시 r을 r0로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.