문제 개요
이 문제에서는 정수 배열이 주어지며, 그중 배열의 다른 요소 중 적어도 하나로 나누어 떨어지는 숫자만 출력해야 합니다.
개념을 더 잘 이해하기 위해 예시를 살펴보겠습니다.
입력 : 3 12 16 21
출력 : 12 21
설명 − 3은 배열에서 가장 작은 수이므로 다른 어떤 수로도 나누어 떨어질 수 없습니다. 12는 3으로 나누어 떨어지고, 16은 3으로 나누어 떨어지지 않으며, 21은 3으로 나누어 떨어집니다. 따라서 3과 16은 제외하고 12와 21만 출력합니다.
접근 방법
가장 단순한 방법은 각 요소에 대해 배열의 다른 모든 요소로 나누어 떨어지는지 일일이 확인하는 것입니다. 하지만 이 방법은 시간 복잡도가 O(n²)으로 비효율적이며, 최선의 해결책이라고 할 수 없습니다.
해시(Hash)를 활용하면 훨씬 효율적으로 문제를 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 배열의 모든 요소를 해시 셋(unordered_set)에 저장하고, 배열의 최댓값을 찾습니다.
- 0이 아닌 각 요소에 대해 자기 자신의 2배부터 최댓값까지 배수를 차례로 확인합니다.
- 확인한 배수가 해시 셋에 존재한다면, 그 요소는 배열의 적어도 하나의 요소로 나누어 떨어지는 것이므로 결과 집합에 추가합니다.
- 같은 값이 두 번 이상 등장하는 경우, 동일한 값끼리는 서로 나누어 떨어지므로 해당 값을 모두 출력 대상에 포함합니다.
이 방식은 에라토스테네스의 체와 유사하게 배수를 건너뛰며 검사하므로, 전체 시간 복잡도는 대략 O(M log M)(M은 배열의 최댓값) 수준입니다. 따라서 요소 개수가 많고 값의 범위가 제한적인 경우 O(n²) 완전 탐색보다 훨씬 빠르게 동작합니다.
예제 코드
이제 위 개념을 바탕으로 프로그램을 작성해 보겠습니다.
#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
출력 설명 − 배열 {2, 4, 7, 12, 14}에서 4는 2로, 12는 2와 4로, 14는 2와 7로 각각 나누어 떨어집니다. 반면 2와 7은 자기 자신 외에는 이를 나누어 떨어지게 하는 요소가 배열에 없으므로 출력에서 제외됩니다. 참고로 결과는 unordered_map의 순회 순서에 따라 정렬되지 않은 상태로 출력될 수 있습니다.