이 글에서는 배열 arr[]와 각각 값 m으로 이루어진 Q개의 쿼리가 주어졌을 때, 배열 안에서 m의 배수에 해당하는 원소의 개수를 구하는 프로그램을 C++로 작성하는 방법을 알아봅니다.
문제 설명
각 쿼리를 처리하려면 배열에서 m으로 나누어 떨어지는 모든 원소를 찾아 그 개수를 세면 됩니다.
예시로 이해하기
입력: arr[] = {4, 7, 3, 8, 12, 15}
Q = 3, query[] = {2, 3, 5}
출력: 3 3 1
결과 해석
쿼리 1: m = 2일 때, 배열에서 2의 배수는 4, 8, 12이므로 개수는 3입니다.
쿼리 2: m = 3일 때, 배열에서 3의 배수는 3, 12, 15이므로 개수는 3입니다.
쿼리 3: m = 5일 때, 배열에서 5의 배수는 15이므로 개수는 1입니다.
해결 방법 1: 단순 순회
가장 직관적인 방법은 쿼리 값 m마다 배열 전체를 한 번씩 순회하면서 m으로 나누어 떨어지는 원소의 개수를 세는 것입니다.
#include <iostream>
using namespace std;
int solveQuery(int arr[], int N, int m){
int count = 0;
for(int i = 0; i < N; i++){
if(arr[i]%m == 0)
count++;
}
return count;
}
int main(){
int arr[] = {4, 7, 3, 8, 12, 15};
int N = sizeof(arr)/sizeof(arr[0]);
int Q = 3;
int query[] = {2, 3, 5};
for(int i = 0; i < Q; i++)
cout<<"배열에서 m의 배수 개수: "<<solveQuery(arr, N,query[i])<<endl;
return 0;
}
출력 결과
배열에서 m의 배수 개수: 3
배열에서 m의 배수 개수: 3
배열에서 m의 배수 개수: 1
이 방식은 쿼리 하나당 배열 전체를 순회하므로 시간 복잡도는 O(Q×n)입니다. 쿼리 개수나 배열 크기가 커지면 성능이 급격히 저하될 수 있습니다.
해결 방법 2: 사전 계산 활용 (에라토스테네스의 체 응용)
더 효율적인 방법은 에라토스테네스의 체와 유사한 방식으로 배수 개수를 미리 계산해 두는 것입니다. 핵심 아이디어는 다음과 같습니다.
- 배열의 최댓값까지 각 값이 등장하는 횟수를 먼저 셉니다.
- 1부터 최댓값까지 각 수 i에 대해, i의 배수 위치에 해당하는 빈도 값을 모두 더해
preCalcCount[i]에 저장합니다. - 이후 쿼리가 들어오면 미리 계산된 배열에서 즉시 답을 조회합니다.
#include <bits/stdc++.h>
using namespace std;
int preCalcCount[10001];
void PreCalculateMultiples(int arr[], int N){
int maxVal = *max_element(arr, arr + N);
int count[maxVal + 1];
memset(count, 0, sizeof(count));
memset(preCalcCount, 0, (maxVal + 1) * sizeof(int));
for (int i = 0; i < N; ++i)
++count[arr[i]];
for (int i = 1; i <= maxVal; ++i)
for (int j = i; j <= maxVal; j += i)
preCalcCount[i] += count[j];
}
int main(){
int arr[] = {4, 7, 3, 8, 12, 15};
int N = sizeof(arr)/sizeof(arr[0]);
int Q = 3;
int query[Q] = {2, 3, 5};
PreCalculateMultiples(arr, N);
for(int i = 0; i < Q; i++)
cout<<"배열에서 m의 배수 개수: "<<preCalcCount[query[i]]<<endl;
return 0;
}
출력 결과
배열에서 m의 배수 개수: 3
배열에서 m의 배수 개수: 3
배열에서 m의 배수 개수: 1
사전 계산 단계에는 대략 O(maxVal × log(maxVal))의 시간이 소요되지만, 일단 준비가 끝나면 이후 각 쿼리는 O(1) 만에 처리됩니다. 따라서 동일한 배열에 대해 수많은 쿼리를 반복해서 처리해야 하는 상황에서는 단순 순회 방식보다 훨씬 유리합니다.