스트림에서 최대 K개 숫자의 평균 구하기 (C++/Java)

스트림에서 숫자의 평균을 구한다는 것은 매번 삽입될 때마다 평균을 계산하는 것을 의미합니다. 하지만 이 문제에서는 스트림에서 최대 K개 숫자의 평균을 구해야 합니다. 즉, 배열에서 K개의 숫자만 선택하여 평균을 계산합니다. 새로운 숫자가 추가될 때, 이 숫자가 평균 계산에 포함되는 K개 숫자 중 하나보다 크면 교체되고, 그렇지 않으면 평균은 그대로 유지됩니다.

예시로 이해하기

입력: n = 4, k = 3, array = {4, 9, 1, 5}, stream = {2, 6, 3, 7}
출력: 6, 6.66, 6.66, 7.33

첫 번째 삽입(2): 초기 상위 3개 숫자는 9, 5, 4 → 평균 = (9+5+4)/3 = 6. 2는 4보다 작으므로 변화 없음.
두 번째 삽입(6): 6 > 4이므로 4를 6으로 교체 → 상위 3개: 9, 6, 5 → 평균 = 20/3 ≈ 6.66
세 번째 삽입(3): 3은 현재 최솟값(5)보다 작으므로 변화 없음 → 평균 = 6.66
네 번째 삽입(7): 7 > 5이므로 5를 7로 교체 → 상위 3개: 9, 7, 6 → 평균 = 22/3 ≈ 7.33

해결 알고리즘

삽입과 삭제가 빈번하게 일어나는 이런 문제에서는 힙(Heap) 자료구조를 사용하는 것이 효율적입니다. 특히 최소 힙(Min Heap)을 유지하면 상위 K개 요소 중 최솟값을 O(1)에 확인할 수 있고, 교체도 O(log K)에 가능합니다.

알고리즘 단계

배열에서 가장 큰 K개 요소를 선택해 최소 힙을 구성합니다. (힙의 루트가 K개 중 최솟값)
이 K개 요소의 합(sum)을 미리 계산해 둡니다.
스트림의 각 요소에 대해 반복합니다:
요소가 힙의 루트(현재 K개 중 최솟값)보다 크면:

루트를 제거하고(poll) 새 요소를 삽입합니다(push).
sum에서 제거된 값을 빼고 새 값을 더합니다.

현재 평균 = sum / K를 계산해 출력합니다.

시간 복잡도

초기 힙 구성: O(n log n) (정렬 후 상위 K개 선택) 또는 O(n + K log n)
각 스트림 요소 처리: O(log K)
전체: O(n log n + m log K) — m은 스트림 길이
공간 복잡도: O(K)

Java 구현 예제

import java.util.*;

public class KMaxAverageStream {
    static void maxAverageKNumbers(int n, int k, int m, int[] arr, int[] query) {
        // 1. 배열 정렬 후 상위 K개를 최소 힙에 저장
        Arrays.sort(arr);
        PriorityQueue minHeap = new PriorityQueue<>();
        double sum = 0;

        for (int i = n - 1; i >= n - k; i--) {
            minHeap.add(arr[i]);
            sum += arr[i];
        }

        // 2. 스트림 처리
        for (int i = 0; i < m; i++) {
            int current = query[i];
            if (current > minHeap.peek()) {
                int removed = minHeap.poll();
                minHeap.add(current);
                sum = sum - removed + current;
            }
            double avg = sum / (double) k;
            System.out.printf("%.2f\n", avg);
        }
    }

    public static void main(String[] args) {
        int n = 4, k = 3, m = 4;
        int[] arr = {4, 9, 1, 5};
        int[] query = {2, 6, 3, 7};

        System.out.println("스트림 처리 후 최대 K개 평균:");
        maxAverageKNumbers(n, k, m, arr, query);
    }
}

실행 결과

스트림 처리 후 최대 K개 평균:
6.00
6.67
6.67
7.33

C++ 구현 예제

#include 
using namespace std;

void maxAverageKNumbers(int n, int k, int m, vector& arr, vector& query) {
    // 내림차순 정렬 후 상위 K개를 최소 힙에 저장
    sort(arr.begin(), arr.end(), greater());
    priority_queue, greater> minHeap;
    double sum = 0;

    for (int i = 0; i < k; i++) {
        minHeap.push(arr[i]);
        sum += arr[i];
    }

    for (int i = 0; i < m; i++) {
        int current = query[i];
        if (current > minHeap.top()) {
            sum -= minHeap.top();
            minHeap.pop();
            minHeap.push(current);
            sum += current;
        }
        cout << fixed << setprecision(2) << (sum / k) << "\n";
    }
}

int main() {
    int n = 4, k = 3, m = 4;
    vector arr = {4, 9, 1, 5};
    vector query = {2, 6, 3, 7};

    cout << "스트림 처리 후 최대 K개 평균:\n";
    maxAverageKNumbers(n, k, m, arr, query);
    return 0;
}

핵심 포인트 요약

자료구조 선택: 상위 K개 유지는 최소 힙이 최적
합계 유지: 매번 평균을 위해 K개 요소를 모두 더하지 말고, 증분적으로 sum 갱신
경계 조건: K > n인 경우, 스트림이 비어있는 경우 등 예외 처리 필요
확장성: 이 패턴은 "슬라이딩 윈도우 최대값", "실시간 상위 K개 추적" 등에도 응용 가능