[level 1] 최대공약수와 최소공배수 - 12940
문제 설명
두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, 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]을 리턴해야 합니다.
출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges
- 제출한 풀이
class Solution {
public int[] solution(int n, int m) {
int[] answer = new int[2];
int gcd_result = gcd(Math.max(m,n),Math.min(m,n));
answer[0] = gcd_result;
answer[1] = m*n/gcd_result;
return answer;
}
public int gcd(int m, int n){
if(m%n == 0) return n;
return gcd(n,m%n);
}
}int 값을 반환하는 gcd메서드를 만들어줬는데 재귀 함수를 이용했다.
basecase인 m%n == 0 인 경우엔 n을 return해주고
basecase에 해당이 되지 않으면 작은 값인 n과 나머지 값으로 m%n==0을 만족할 때까지 gcd메서드를 호출해준다.
Math.max,Math.min을 이용해 gcd에는 둘 중 더 큰 값을 m으로 작은 값을 n으로 파라미터 값으로 준다.
answer 배열에 첫번째 값은 최대공약수 값을 gcd 메서드를 이용해서 담아줬다.
answer 배열에 두번째 값은 최소공배수 값을 담아줄건데
m*n = 최대공약수*최소공배수 임을 이용해 담아준다.
🐾
이 문제를 풀려고 여러 번 시도하다가 결국 검색해봤다..
유클리드 호제법과 재귀 함수를 이용한 경우가 많아서 두 부분을 먼저 공부했는데 이 문제를 풀면서 두 개념을 조금 더 자세하게 알 수 있어서 좋았다.
풀이는 많이 참고했지만.. 그래도.. 공부를 했으니 만족하고 다음 문제는 더 잘 풀 수 있었으면 좋겠다..
