프로그래머스 - 최대공약수와 최소공배수, 유클리드 호제법 java

12940번 문제

코딩테스트 연습 - 최대공약수와 최소공배수 | 프로그래머스 (programmers.co.kr)

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

 

---

풀이

• 생각

최대공약수를 구하는 유클리드 호제법을 활용

최소공배수 = n * m / 최대공약수

 

• 1번 풀이

public int[] solution(int n, int m) {		
	int gcd = gcd(n, m%n);
	int lcm = n * m / gcd;

	return new int[] {gcd, lcm};
}

public int gcd(int a, int r) {
	return (r == 0) ? a : gcd(r, a%r);
}

✔️ 유클리드 호제법

- 32 와 46의 최대공약수를 구한다고 가정한다.

- 47을 32으로 나누면 나머지는 14이다.

- 32를 14로 나누면 나머지가 4이다.

- 14를 4로 나누면 나머지가 2이다.

- 4를 2로 나누면 나머지가 0이다.  ✅ 그러므로 최대공약수는 2이다.

위 공식을 재귀함수 gcd() 로 구현

 

• 2번 풀이

public int[] solution(int n, int m) {
	int gcd = BigInteger.valueOf(m).gcd(BigInteger.valueOf(n)).intValue();
	int lcm = n * m / gcd;

	return new int[] { gcd, lcm };
}

✔️ BigInteger 의 gcd 메소드를 활용하면 최대공약수를 바로 구할 수 있다.