최대공약수와 최소공배수

프로그래머스 1단계 Java 최대공약수와 최소공배수 문제입니다.

---

문제 설명

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

 

문제 해결 방법

① 입력받은 두 수 중 작은 수를 첫번째 인덱스, 큰 수를 두번째 인덱스에 초기화

② 작은 수로 큰 수를 나누었을 때 나머지를 확인

    ⑴ 0일 경우 ▶ 각각 최소공배수, 최대공약수이므로 배열 반환

    ⑵ 0이 아닐 경우 ▶ 재귀함수 호출 - 작은 수를 첫번째 인자, 나눈 나머지 값을 두번째 인자

③ 나머지가 0이 되어 배열을 반환할 때까지 재귀(반환된 배열의 첫번째 인덱스 값이 최대공약수)

④ 다음의 공식을 이용하여 최소공배수를 계산

    ▶ 최소공배수 = (두 수의 곱) / 최대공약수

---

class Solution {
    public int[] solution(int n, int m) {
        // ① 입력받은 두 수 중 작은 수를 첫번째 인덱스, 큰 수를 두번째 인덱스에 초기화
        int[] answer = n < m ? new int[] { n, m } : new int[] { m, n };
        // ② 작은 수로 큰 수를 나누었을 때 나머지를 확인
        if (answer[1] % answer[0] == 0)
			// ⑴ 0일 경우 ▶ 각각 최소공배수, 최대공약수이므로 배열 반환
			return answer;
		else {
			// ⑵ 0이 아닐 경우 ▶ 재귀함수 호출 - 작은 수를 첫번째 인자, 나눈 나머지 값을 두번째 인자
			answer = solution(answer[0], answer[1] % answer[0]);
		}
		// ③ 나머지가 0이 되어 배열을 반환할 때까지 재귀(반환된 배열의 첫번째 인덱스 값이 최대공약수)
		
        // ④ 다음의 공식을 이용하여 최소공배수를 계산
        // ▶ 최소공배수 = (두 수의 곱) / 최대공약수
        answer[1] = n * m / answer[0];

		return answer;
    }
}

---

※ 삼항연산자

②③ 의 반환값은 삼항연산자로 값을 정하게 되는데, if/else 문과 매우 흡사하여 코드가 간결해지는데에 도움이 됩니다.

삼항연산자 사용법은 다음과 같으며, 참 또는 거짓의 값을 반드시 반환하는 것이 if/else 문과의 차이점입니다.

Condition ? TRUE : FALSE

if/else 문에 비해 구문이 간단하다해서 속도가 빠른 것은 아닙니다.

 

※ 유클리드 호제법

유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나입니다. 

이는 명시적으로 기술된 가장 오래된 알고리즘으로서도 알려져 있습니다.

최대공약수를 구하는 문제에 있어서 도움이 되므로 한번쯤은 짚고 넘어가시는걸 추천합니다.

 

유클리드 호제법 > https://ko.wikipedia.org/wiki/유클리드_호제법

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

※ 위 코드는 해결 방법 중 한가지이며 더 효율적인 코드가 있을 수 있습니다.

 

문제 풀어보기 ▶ https://programmers.co.kr/learn/courses/30/lessons/12940?language=java

코딩테스트 연습 - 최대공약수와 최소공배수