C++에서 소수 빈도를 가진 배열 요소 찾는 방법

개요

배열(Array)은 동일한 데이터 타입의 요소들을 담는 컨테이너 자료구조입니다.

소수 빈도(Prime Frequency)란 배열 내 특정 요소의 등장 횟수가 소수(prime number)인 경우를 의미합니다.

이 두 개념을 바탕으로, 이번 글에서 다룰 문제는 소수 빈도를 가진 배열 요소 찾기입니다. 문자열이 주어지면 각 문자의 등장 횟수(빈도)를 계산하고, 해당 빈도가 소수인지 판별한 뒤, 소수 빈도를 가진 문자의 개수를 세는 것이 목표입니다.

예제

Input: str = "helloworld"
Output: 2

설명

각 문자의 등장 횟수는 다음과 같습니다.

h -> 1
e -> 1
l -> 3
o -> 2
w -> 1
r -> 1
d -> 1

'l'은 3번, 'o'는 2번 등장하는데, 3과 2는 모두 소수입니다. 따라서 소수 빈도를 가진 요소는 2개이며, 출력값은 2가 됩니다.

접근 방법

문자열을 순차적으로 탐색하면서 C++의 unordered_map을 사용해 각 문자의 등장 횟수를 기록합니다. 이후 맵에 저장된 각 빈도 값이 소수인지 검사하고, 소수라면 결과 카운트를 1씩 증가시킵니다.

알고리즘

1. 빈도를 저장할 unordered_map<char, int>을 선언합니다.
2. 문자열을 한 번 순회하며 각 문자의 개수를 증가시킵니다.
3. 맵을 순회하면서 각 빈도 값에 대해 소수 판별 함수를 호출합니다.
4. 빈도가 소수이면 카운트를 증가시킵니다.
5. 최종 카운트를 반환합니다.

소수 판별은 1과 자기 자신 외에는 약수를 가지지 않는지 확인하는 과정으로, 연산량을 줄이기 위해 √n까지만 검사하는 6k±1 최적화 기법을 적용했습니다.

C++ 구현 코드

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// 소수 판별 함수
int check_prime(int n) {
    if (n <= 1)
        return 0;
    if (n <= 3)
        return 1;
    if (n % 2 == 0 || n % 3 == 0)
        return 0;
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return 0;
    return 1;
}

// 소수 빈도를 가진 요소 개수 세기
int countPrimeFrequent(string s) {
    int count = 0;
    unordered_map<char, int> mp;
    for (int i = 0; i < s.length(); i++)
        mp[s[i]]++;
    for (auto it = mp.begin(); it != mp.end(); it++) {
        if (check_prime(it->second))
            count++;
    }
    return count;
}

int main() {
    string s = "helloworld";
    cout << countPrimeFrequent(s);
    return 0;
}

출력 결과

소수 빈도를 가진 요소의 개수 : 2

복잡도 분석

시간 복잡도는 O(n + k·√m)입니다. 여기서 n은 문자열의 길이, k는 서로 다른 문자의 개수, m은 최대 빈도 값을 의미합니다. 공간 복잡도는 O(k)로, 서로 다른 문자의 수에 비례합니다.