1. 개요
이 사용방법(예제)에서는 주어진 정수의 모든 요소를 찾는 Java 프로그램을 작성합니다.
2. 문제 소개
Java 코드 작성을 시작하기 전에 정수의 요소가 무엇인지 이해해 봅시다.
정수 n 이 주어지면 정수 i 는 숫자 i 를 완전히 나눌 수 있는 경우 n 의 인수 입니다. 여기서 완전히 나눌 수 있다는 것은 n 을 i 로 나눌 때 나머지가 0이라는 것을 의미합니다.
몇 가지 예를 통해 빠르게 설명할 수 있습니다.
- n = 10 , 인수: 1, 2, 5 , 10
- n = 13 , 인수: 1 및 13
- n = 1 , n 은 하나의 인자만 가집니다: 1
- n = 0 , 0에는 인수가 없습니다.
예에서 볼 수 있듯이 일반적으로 정수 n 의 약수는 n 이 소수(예: 13 )인 경우에도 항상 1 과 n 을 포함합니다 . 그러나 0은 특수 정수입니다. 요인이 없습니다.
이제 인수의 개념을 이해했으므로 주어진 정수의 모든 인수를 찾는 Java 프로그램을 작성해 보겠습니다.
간단하게 하기 위해 단위 테스트 어설션을 사용하여 솔루션이 예상대로 작동하는지 확인합니다.
3. 정수의 모든 인수를 찾는 방법 만들기
정수 n 의 모든 인수를 찾는 가장 간단한 방법은 1에서 n 까지 반복 하고 어떤 숫자가 n 을 완전히 나눌 수 있는지 테스트하는 것 입니다. n 을 완전히 나눌 수 있는 숫자를 Set 에 저장할 수 있습니다 . 루핑이 완료되면 이 Set 은 n 의 모든 인수를 보유합니다 .
Java에서 이 아이디어를 구현하는 것은 우리에게 어려운 일이 아닙니다.
static Set<Integer> getAllFactorsVer1(int n) {
Set<Integer> factors = new HashSet<>();
for (int i = 1; i <= n; i++) {
if (n % i == 0) {
factors.add(i);
}
}
return factors;
}
다음으로 우리의 방법이 예상대로 작동하는지 확인하기 위한 몇 가지 테스트를 작성해 보겠습니다. 먼저, 테스트할 숫자와 예상 요인을 준비하기 위해 맵 을 생성해 보겠습니다.
final static Map<Integer, Set<Integer>> FACTOR_MAP = ImmutableMap.of(
0, ImmutableSet.of(),
1, ImmutableSet.of(1),
20, ImmutableSet.of(1, 2, 4, 5, 10, 20),
24, ImmutableSet.of(1, 2, 3, 4, 6, 8, 12, 24),
97, ImmutableSet.of(1, 97),
99, ImmutableSet.of(1, 3, 9, 11, 33, 99),
100, ImmutableSet.of(1, 2, 4, 5, 10, 20, 25, 50, 100)
);
이제 위의 FACTOR_MAP 의 각 숫자에 대해 구현한 getAllFactorsVer1() 메서드를 호출 하여 원하는 요소를 찾을 수 있는지 확인합니다.
FACTOR_MAP.forEach((number, expected) -> assertEquals(expected, FactorsOfInteger.getAllFactorsVer1(number)));테스트를 실행하면 통과합니다. 따라서 이 방법은 문제를 해결합니다. 훌륭합니다!
예리한 눈으로 우리가 Ver1으로 메서드 이름을 지정했음을 알아차릴 수 있습니다. 일반적으로 이는 사용방법(예제)에서 다른 버전을 소개할 것임을 의미합니다. 즉, 솔루션에는 여전히 개선의 여지가 있습니다.
다음으로 버전 1 구현을 최적화하는 방법을 살펴보겠습니다.
4. 최적화 - 버전 2
메서드의 기본 논리를 검토해 보겠습니다.
for (int i = 1; i <= n; i++) {
if (n % i == 0) {
factors.add(i);
}
}위의 코드에서 볼 수 있듯이 n % i 계산을 n 번 실행합니다. 이제 정수의 인수를 살펴보면 인수가 항상 쌍으로 나온다는 것을 알 수 있습니다 . 이 요소 특성을 이해하기 위해 n =100 을 예로 들어 보겠습니다.
1 2 4 5 10 20 25 50 100
│ │ │ │ | │ │ │ │
│ │ │ │ [10,10] │ │ │ │
│ │ │ │ │ │ │ │
│ │ │ └──[5, 20] ─┘ │ │ │
│ │ │ │ │ │
│ │ └───────[4, 25]────────┘ │ │
│ │ │ │
│ └────────────[2, 50]──────────────┘ │
│ │
└─────────────────[1, 100]───────────────────┘
우리가 본 것처럼 100 의 모든 인수 는 쌍입니다. 따라서 n 의 하나의 요소 i 를 찾은 경우 i'= n/i 쌍을 얻을 수 있습니다 . 즉, 우리는 n 번 반복할 필요가 없습니다. 대신, 1에서 숫자 n 의 제곱근까지 확인하고 모든 i 및 i' 쌍을 찾습니다. 이런 식으로 주어진 n=100 에서 우리는 10번만 반복합니다.
다음으로 버전 1 방법을 최적화해 보겠습니다.
static Set<Integer> getAllFactorsVer2(int n) {
Set<Integer> factors = new HashSet<>();
for (int i = 1; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
factors.add(i);
factors.add(n / i);
}
}
return factors;
}
위의 코드에서 볼 수 있듯이 Java 표준 라이브러리 의 Math.sqrt() 메서드를 사용하여 n 의 제곱근을 계산했습니다 .
이제 동일한 테스트 데이터로 두 번째 버전의 구현을 테스트해 보겠습니다.
FACTOR_MAP.forEach((number, expected) -> assertEquals(expected, FactorsOfInteger.getAllFactorsVer2(number)));테스트를 실행하면 통과합니다. 따라서 최적화된 버전 2는 예상대로 작동합니다.
요인 결정 시간을 n 에서 n 의 제곱근으로 성공적으로 줄였습니다. 상당한 개선입니다. 그러나 여전히 추가 최적화의 여지가 있습니다. 그럼, 다음으로 더 분석해 봅시다.
5. 추가 최적화 – 버전 3
먼저 간단한 수학 분석을 수행해 보겠습니다.
아시다시피 주어진 정수 n 은 짝수이거나 홀수일 수 있습니다. n 이 짝수 이면 인수가 짝수인지 홀수인지 단정할 수 없습니다. 예를 들어, 20의 약수는 1, 2, 4, 5, 10, 20입니다. 따라서 짝수와 홀수가 있습니다.
그러나 n 이 홀수이면 모든 인수도 홀수여야 합니다 . 예를 들어, 99의 약수는 1, 3, 9, 11, 33, 99입니다. 따라서 모두 홀수입니다.
따라서 n 이 홀수 인지 여부에 따라 루프의 증분 단계를 조정할 수 있습니다 . 루프가 i = 1 에서 시작 하므로 홀수가 주어지면 증가 단계 = 2 로 설정하여 모든 짝수에 대한 검사를 건너뛸 수 있습니다.
다음으로 이 아이디어를 버전 3에서 구현해 보겠습니다.
static Set<Integer> getAllFactorsVer3(int n) {
Set<Integer> factors = new HashSet<>();
int step = n % 2 == 0 ? 1 : 2;
for (int i = 1; i <= Math.sqrt(n); i += step) {
if (n % i == 0) {
factors.add(i);
factors.add(n / i);
}
}
return factors;
}
이 최적화를 통해 n 이 짝수인 경우 루프는 버전 2와 동일하게 sqrt(n) 번 실행됩니다.
그러나 n 이 홀수이면 루프는 총 sqrt(n)/2 번 실행됩니다.
마지막으로 버전 3 솔루션을 테스트해 보겠습니다.
FACTOR_MAP.forEach((number, expected) -> assertEquals(expected, FactorsOfInteger.getAllFactorsVer3(number)));테스트를 실행하면 통과합니다. 따라서 작업을 올바르게 수행합니다.
6. 결론
이 기사에서는 정수의 모든 인수를 찾는 Java 메서드를 만들었습니다. 또한 초기 솔루션에 대한 두 가지 최적화에 대해 논의했습니다.
늘 그렇듯이 여기에 제시된 모든 코드 스니펫은 GitHub에서 사용할 수 있습니다.
