[백준] 최대공약수와 최소공배수 (BufferedReader, StringTokenizer, 유클리드 호제법)

▶ BufferedReader, StringTokenizer, 유클리드 호제법을 활용한 간단한 문제가 있어 정리해보고자 합니다.

 

문제설명

입력 & 출력

나의 풀이

 

이번 문제는 간단하게 최대공약수와 최소공배수를 구현할 수 있는지 알아보는 문제입니다.

 

최소 공배수를 구하기 위해선 최대 공약수를 먼저 구해야 합니다.

 

최대 공약수를 구하기 위하여 gcd() 함수를 선언해주고, 유클리드 호제법으로 구현했습니다.

 

먼저 유클리드 호제법을 사용하기 위해선 큰 값과 작은 값을 구해줘야 합니다. Math클래스의 min()과 max() 메소드를 사용하여 구해줍니다.

 

유클리드 호제법은 나머지가 0이기 전 값을 반환해야 하기 때문에 일 때 큰 값을 반환해 주도록 if문으로 분기처리 해줬습니다.

 

만약에 0을 구하지 못했으면 다시 제귀호출하여 나머지가 0이 될 때까지 제귀호출 해줍니다.

 

예를 들어 설명하자면 다음과 같습니다.

24 18이 입력으로 들어올 때

large = 24, small = 18

small = 18  small이 0이 아니기 때문에 다시 gcd를 호출합니다.24 % 18  ➡ gcd(18,6)

 

large = 18, small = 6

small = 6  small이 0이 아니기 때문에 다시 gcd를 호출합니다. ➡ gcd(6,0)

 

large = 6, small = 0

small = 0 small이 0이므로 large인 6이 최대공약수가 됩니다.

 

gcd() 함수를 통해 얻은 최대공약수를 사용해서 최소 공배수를 구해서 반환하여 마무리해줍니다.

 

다른 풀이✅

 

이번 풀이에서는 재귀 호출이 아닌 반복문을 사용했습니다.

 

24 18이 입력으로 들어올 때

 

tmp = 6

a = 18

b = 8 ➡ b가 0이 아니기 때문에 다시 반복

 

tmp = 18 % 6 = 0

a = 6

b = 0 ➡ b가 0이므로 a반환

 

 

참고 ❗

 

[JAVA] 입출력, BufferedReader, StringTokenizer

[Algorithm] 유클리드 호제법(최대공약수 gcd) 알아보기