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

프로그래머스 > 코딩테스트 연습 > 연습문제 > 최대공약수와 최소공배수

https://school.programmers.co.kr/learn/courses/30/lessons/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]을 리턴해야 합니다.

---

💻 소스코드

public class Solution {
    public int[] solution(int n, int m) {
        int a = n;
        int b = m;
        
        while(a !=0)
        {
            int r = b%a;
            b = a;
            a = r;
        }
        int GCD = b;
        int LCM = (n*m)/GCD;

        return new int[]{GCD, LCM};
    }  
}

 

 

다른 풀이

public class Solution {
    public int[] solution(int n, int m) {
        int GCD = gcd(n,m);
        int LCM = (n*m)/GCD;
        
        return new int[]{GCD, LCM};
    }
    
    private int gcd(int n, int m)
    {
        return n == 0 ? m : gcd(m%n, n);
    }
}

 

📝 풀이

최소공배수를 구하는 법은 두 수 n과 m이 있을때 m을 n으로 나눈 나머지가 r이면,

m은 n으로 바꾸고 n은 r로 바꿔서 r이 0이 될때 까지 반복한다. 나머지가 0일때 n이 최소 공배수가 된다.

최대공약수는 (n*m)/최소공배수로 구할 수 있다.

 

첫 풀이는 while 반복문을 사용해서 문제를 해결했다.

최대공약수를 구할때 원본을 사용해야함으로 n과 m을 a와 b에 담아주고 최소공배수를 구하는 식을 적용했다.

 

다른 사람의 풀이를 찾다 재귀함수를 사용한 것을 찾아서 적용해 보았다.

정수 n과m을 매개변수로 받는 함수에서 n == 0이라면 m이 최소공약수임으로 m을 리턴하고 그게 아니면 n에 m%n을 m에 n을 다시 넘겼다.

 

재귀함수를 잘사용하면 변수의 사용이 적어지고, 가독성이 올라가는 장점이 있지만 무한 반복에 빠지면 스택 오버플로우가 발생하는 큰 단점이 있다. 따라서 재귀 함수를 사용할 때 어느정도 함수를 호출하게 될 지 예측을 하고 안전하게 사용해야한다.

 

※ 참고 사이트

최대공약수, 최소공배수 : https://xn--yq5bk9r.com/blog/math-gcd-lcm

재귀함수 vs 반복문 : https://yeonjewon.tistory.com/80

---

관련 포스팅