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

최대공약수와 최소공배수

오늘은 "최대공약수와 최소공배수" 문제를 풀어보도록 하겠습니다. 바로 문제 살펴보겠습니다.

 

문제 설명

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, 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[] answer = new int[] {};
        return answer;
    }
}

 

나의 풀이

using System;
public class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        int min;
        int max;
        
        min = gcd(n, m);
        max = (n * m) / min;
        
        answer[0] = min;
        answer[1] = max;
        return answer;
    }
    
    public int gcd(int n, int m)
    {
        if(m == 0) return n;
        else return gcd(m, n%m);
    }
}

 

코드 분석

int형 n, m이 주어지며 코드가 시작됩니다. int형 배열 answer에는 배열의 크기를 2로 설정해주고, int형 min과 max를 선언합니다. 메인함수 바깥에 n과 m을 매개변수로 받는 gcd함수를 생성합니다. 함수안에는 if문으로 m이 0이면 n을 리턴하고, 아니라면 gcd(m, n%m)을 리턴하도록 되어있습니다. min에는 gcd(n, m)을, max에는 (n * m) / min을 넣어줍니다. answer 배열에 0번째와 1번째 인덱스에 각각 min과 max를 넣어주고 answer 값을 리턴합니다.

 

풀이 설명

이번 문제에서 유심히 살펴봐야 할 것은 gcd()함수 입니다. 이것은 최대공약수 최소공배수를 다루는 문제에서 사용되는 유클리드 호재법 알고리즘을 적용한 것입니다. 이 알고리즘에서는 재귀함수가 사용되는 데, 함수안에서 같은 함수를 다시 실행하여 반복하도록 하는 방법입니다. 유클리드 호재법은 사용하는 공식이 정해져있습니다. 

// 최대공약수 재귀 함수. 한쪽이 0이 될 때까지 스왑하면서 나머지를 구한다.
public int gcd(int a, int b)
{
     if(b == 0) return a;
     else return gcd(b, a % b);
}

위에서도 같은 방식으로 사용되었지만, 보기 쉽도록 표현했습니다. 위 공식에서 보면 gcd함수 안에서 gcd함수를 매개변수만 바꿔준 뒤에 다시 실행하도록 else문에 정의되어 있습니다. 해당 형태를 가지는 것이 재귀함수 입니다.

 

<NEXT>

오늘은 간단하지만, 알고 있으면 꽤나 유용한 유클리드 호재법, 재귀함수에 대해 "최대공약수와 최소공배수" 문제를 풀어보면서 알아보았습니다. 다음에는 월간 코드 챌린지 시즌1 출제문제 중 하나인 "3진법 뒤집기" 문제를 다뤄보도록 하겠습니다. 감사합니다.