반응형
백준 문제에서 최대공약수를 찾는 문제가 나왔어요. 당연히 무식한 저는 그냥 두 수의 모든 배수를 찾아서 그 중에서 가장 큰 수를 검색하는 방식으로 했는데 시간초과에 걸리는 것이 아니겠어요? 그래서 그럼 어떤 방법으로 최대공약수를 찾을 수 있을까 찾아봤더니 유클리드 호제법이라는 아주 유명한 수학공식이 있더군요.
1. 무식한 방법
public static int maximumCommonMultiple(Integer a, Integer b) {
Map<Integer, Integer> aCommonMultiple = new HashMap<>();
List<Integer> bCommonMultiple = new ArrayList<>();
int resultCommonMultiple = 0;
for (int i = 1; i <= a; i++) {
if ((a % i) == 0) {
aCommonMultiple.put(i, 0);
}
}
for (int i = 1; i <= b; i++) {
if((b % i) == 0) {
bCommonMultiple.add(i);
}
}
for (int i = bCommonMultiple.size() - 1; i >= 0; i--) {
if (aCommonMultiple.containsKey(bCommonMultiple.get(i))) {
resultCommonMultiple = bCommonMultiple.get(i);
return resultCommonMultiple;
}
}
return resultCommonMultiple;
}
입력받은 두 수를 하나는 Map, 하나는 List에 각자의 배수를 넣고, List를 순회하면서 가장 큰 같은 배수를 찾아서 리턴으로 반환하는 코드입니다. 아무래도 입력받은 두 수의 배수를 찾는 것부터 많은 1부터 그 수의 끝까지 반복을 해야하기 때문에 시간이 굉장히 많이 걸리는 단점이 있고, 실제로도 백준 문제에서 시간초과를 받았습니다 ㅠ
유클리드 호제법
public static int maximumCommonMultiple(Integer a, Integer b) {
if (b == 0) {
return a;
}
return maximumCommonMultiple(b, a % b);
}
코드가 굉장히 많이 줄었어요. 계속해서 b로 a를 나눈 나머지를 b 자리에 b를 a 자리에 넣어서 재귀호출을 하고, a를 b로 나눈 나머지가 0일때 a가 최대 공약수입니다. 이것의 증명은 아래의 링크 나무위키에 가서 보세요. 저는 이해가 안되요...
자바로 손쉽게 최대공약수를 찾는 방법에 대해서 알아보았습니다.
반응형
'IT Tech > Java' 카테고리의 다른 글
Spring Data JPA - Specification이란? (0) | 2024.03.25 |
---|---|
JPA의 영속성 전파 cascade 옵션에 대해서 알아보기 (0) | 2024.01.17 |
자바(JAVA)의 Map에서 키와 값으로 요소 찾기 - containsKey와 containsValue 활용하기 (0) | 2024.01.09 |
QuickSort에 대해서 알아봅시다~ Java Array, List 정렬 구현하기 (1) | 2024.01.02 |