이 문제에서는 정수 배열이 주어지며 배열의 다른 요소 중 하나 이상으로 나눌 수 있는 숫자만 인쇄해야 합니다.
개념을 더 잘 이해할 수 있도록 예를 들어 보겠습니다.
Input : 3 12 16 21 Output : 12 21
설명 − 3은 가장 작은 수이므로 다른 어떤 수로도 나눌 수 있습니다. 3으로 나눌 수 있는 12, 3으로 나눌 수 없는 16, 3으로 나누어 떨어지는 21입니다. 따라서 3과 16은 무시하겠습니다.
한 가지 쉬운 방법은 모든 요소가 배열의 다른 요소로 나눌 수 있는지 여부를 확인하는 것입니다. 그러나 이것은 문제에 대한 최상의 솔루션이 아닙니다.
해시 사용 더 나은 솔루션이 될 수 있습니다. 배열의 요소를 해시에 저장한 다음 배열의 최대 요소를 찾습니다. 그런 다음이 최대 요소는 주어진 숫자의 배수를 찾고 해시에서 다중이 발견되면 요소는 배열의 적어도 하나의 요소로 나뉩니다. 이와 같이 배열의 적어도 하나의 요소로 나누어진 요소를 출력합니다.
예시
이제 이 개념을 기반으로 프로그램을 만들 수 있습니다. −
#include <bits/stdc++.h>
using namespace std;
void printDivisibleNumber(int arr[], int n){
unordered_set<int> s;
int maxElement = INT_MIN;
for (int i = 0; i < n; i++) {
s.insert(arr[i]);
maxElement = max(maxElement, arr[i]);
}
unordered_set<int> res;
for (int i = 0; i < n; i++) {
if (arr[i] != 0) {
for (int j = arr[i] * 2; j <= maxElement; j += arr[i]) {
if (s.find(j) != s.end())
res.insert(j);
}
}
}
unordered_map<int, int> mp;
for (int i = 0; i <n; i++)
mp[arr[i]]++;
unordered_map<int, int>::iterator it;
vector<int> ans;
for (it = mp.begin(); it != mp.end(); it++) {
if (it->second >= 2) {
if (res.find(it->first) == res.end()) {
int val = it->second;
while (val--)
ans.push_back(it->first);
}
}
if (res.find(it->first) != res.end()) {
int val = it->second;
while (val--)
ans.push_back(it->first);
}
}
for (auto x : ans)
cout<<x<<"\t";
}
int main(){
int arr[] = {2, 4, 7 , 12 , 14 };
int n = sizeof(arr) / sizeof(arr[0]);
printDivisibleNumber(arr, n);
return 0;
} 출력
12 14 4