배열에서 소수 번 등장하는 요소의 개수 구하기

배열이 하나 주어졌을 때, 그중 소수(Prime Number)번 만큼 등장하는 요소가 몇 개인지 세는 문제를 살펴보겠습니다.

예를 들어 배열이 {1, 2, 2, 0, 1, 5, 2, 5, 0, 0, 1, 1}이라고 가정해 봅시다. 각 숫자의 등장 횟수는 다음과 같습니다.

• 1은 4번 등장
• 2는 3번 등장
• 0은 3번 등장
• 5는 2번 등장

여기서 등장 횟수가 소수인 요소는 3번 등장한 2와 0, 그리고 2번 등장한 5로 총 3개입니다. 따라서 정답은 3이 됩니다. 참고로 4는 소수가 아니므로 1은 제외됩니다.

알고리즘

countPrimeOccurrence(arr, n)

Begin
    count := 0
    define map with int type key and int type value
    for each element e in arr, do
        increase map.key(arr).value
    done
    for each key check whether the value corresponding the value is prime or not, if prime, then increase count.
    return count
End

알고리즘 동작 방식

1. 각 요소의 빈도수를 저장하기 위해 맵(Map) 자료구조를 준비합니다.
2. 배열을 한 번 순회하면서 각 요소의 등장 횟수를 맵에 기록합니다.
3. 맵의 각 값(빈도수)이 소수인지 판별하고, 소수라면 카운트를 증가시킵니다.
4. 최종 카운트를 반환합니다.

C++ 구현 예제

#include <iostream>
#include <map>
using namespace std;
bool isPrime(int n){
    for(int i = 2; i<=n/2; i++){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}
int countPrimeOcurrence(int arr[], int n){
    int count = 0;
    map<int, int> freq_map;
    for(int i = 0; i<n; i++){
        freq_map[arr[i]]++; //increase the frequency
    }
    for (auto it = freq_map.begin(); it != freq_map.end(); it++) {
        if (isPrime(it->second))
            count++;
    }
    return count;
}
int main() {
    int arr[] = {1, 2, 2, 0, 1, 5, 2, 5, 0, 0, 1, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Prime frequency count: " << countPrimeOcurrence(arr, n);
}

코드 설명

• isPrime(n): 2부터 n/2까지의 수로 나누어 떨어지는지 확인하여 소수 여부를 판별하는 함수입니다.
• countPrimeOcurrence(arr, n): 맵을 이용해 각 요소의 빈도수를 계산한 뒤, 빈도수가 소수인 경우의 개수를 반환합니다.

실행 결과

Prime frequency count: 3

시간 복잡도는 배열 순회에 O(n), 빈도수 판별에 O(k·√m)(k는 서로 다른 요소 수, m은 최대 빈도수)이 소요되며, 전체적으로 효율적인 편입니다.