C++에서 첫 등장 이후 최소 K번 이상 나타나는 배열 요소 개수 세기

문제 소개

이 글에서는 배열 내 요소 중 첫 등장 이후 최소 K번 이상 다시 나타나는 요소의 개수를 구하는 프로그램을 C++로 작성해 보겠습니다.

문제의 조건은 다음과 같습니다. 정수형 배열과 값 k가 주어졌을 때, 각 요소를 기준으로 그 이후에 위치한 요소들 가운데 해당 요소와 같은 값이 k번 이상 등장하면 그 요소를 카운트합니다.

접근 방법

이 문제는 다음과 같은 단계로 해결할 수 있습니다.

배열의 각 요소를 순회하면서 이미 확인한 적 있는 값인지 검사하여 중복 계산을 방지합니다.
처음 만나는 값이라면, 그 뒤에 있는 요소들을 탐색하며 같은 값이 몇 번 나오는지 셉니다.
등장 횟수가 k 이상이면 결과값을 1 증가시킵니다.
중복 방지를 위해 map 자료구조를 활용합니다.

C++ 코드 예시

#include <iostream>
#include <map>
using namespace std;

// 조건을 만족하는 요소의 개수를 반환하는 함수
int calc_count(int n, int arr[], int k){
    int cnt, ans = 0;
    // 중복 제거를 위한 맵
    map<int, bool> hash;
    for (int i = 0; i < n; i++) {
        cnt = 0;
        // 이미 확인한 값은 건너뜀
        if (hash[arr[i]] == true)
            continue;
        hash[arr[i]] = true;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] == arr[i])
                cnt++;
            // k개 이상 발견되면 탐색 종료
            if (cnt >= k)
                break;
        }
        if (cnt >= k)
            ans++;
    }
    return ans;
}

int main(){
    int arr[] = { 1, 2, 1, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 1;
    cout << calc_count(n, arr, k);
    return 0;
}

출력 결과

코드 설명

위 코드를 단계별로 살펴보겠습니다.

calc_count() 함수는 배열의 크기 n, 배열 arr, 기준값 k를 매개변수로 받습니다.
map<int, bool> 타입의 hash 변수는 한 번 확인한 값을 기록하여 동일한 값에 대한 중복 계산을 막아줍니다.
바깥쪽 반복문은 배열의 각 요소를 순회하고, 안쪽 반복문은 현재 요소 이후의 값들 중 같은 값이 몇 번 나오는지 셉니다.
카운트가 k에 도달하면 불필요한 탐색을 줄이기 위해 안쪽 반복문을 즉시 종료합니다(break).
최종적으로 조건을 만족하는 서로 다른 값의 개수를 반환합니다.

예제에서 배열은 {1, 2, 1, 3}이고 k = 1입니다. 값 1은 첫 등장 이후 한 번 더 나타나므로 조건을 충족하고, 2와 3은 뒤에서 다시 등장하지 않으므로 제외됩니다. 따라서 결과는 1이 됩니다.

시간 복잡도

이 알고리즘은 각 요소마다 뒤따르는 요소들을 탐색하므로 최악의 경우 시간 복잡도는 O(n²)입니다. 배열의 크기가 크다면 해시맵을 사용해 전체 빈도를 미리 계산한 뒤 누적 등장 횟수를 비교하는 방식으로 성능을 O(n) 수준까지 개선할 수 있습니다.