숫자로 이루어진 리스트 nums가 주어졌을 때, 이 리스트에서 만들 수 있는 모든 홀수 길이 부분 배열(sublist)의 중앙값들을 모두 더한 합계를 구하는 문제입니다.
예를 들어 입력이 nums = [2, 4, 6, 3]이라면 출력은 23이 됩니다. 홀수 길이 부분 배열은 다음과 같습니다.
- 길이 1: [2], [4], [6], [3]
- 길이 3: [2, 4, 6], [4, 6, 3]
각 부분 배열의 중앙값은 순서대로 2, 4, 6, 3, 4, 4이므로, 이들의 합은 2 + 4 + 6 + 3 + 4 + 4 = 23입니다.
문제 해결 접근 방식
이 문제는 최대 힙(max-heap)과 최소 힙(min-heap), 두 개의 우선순위 큐를 사용하면 효율적으로 해결할 수 있습니다. 최대 힙에는 작은 쪽 절반의 값을, 최소 힙에는 큰 쪽 절반의 값을 저장하여, 최대 힙의 루트 값이 항상 현재 구간의 중앙값이 되도록 유지합니다.
알고리즘 단계
- 결과를 저장할 변수
ret을 0으로 초기화합니다. - 시작 인덱스
i를 0부터 배열 끝까지 반복합니다.- 매 반복마다 최대 힙
que_max와 최소 힙que_min을 새로 생성합니다. - 끝 인덱스
j를i부터 배열 끝까지 반복하며 다음을 수행합니다.nums[j]를 최대 힙que_max에 삽입합니다.- 두 힙의 크기 차이가 2 이상이 되지 않도록,
que_max의 루트를que_min으로 옮겨 균형을 맞춥니다. que_min이 비어 있지 않으면서que_max의 루트가que_min의 루트보다 크다면, 두 힙의 루트 값을 서로 교환합니다. 이렇게 하면que_max에는 항상 작은 값들이,que_min에는 큰 값들이 위치하게 됩니다.i와j의 홀짝성이 같다는 것은 현재 부분 배열[i..j]의 길이가 홀수라는 의미이므로, 이때 최대 힙의 루트 값(중앙값)을ret에 더합니다.
- 매 반복마다 최대 힙
- 모든 반복이 끝나면
ret을 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int>& nums) {
int ret = 0;
for (int i = 0; i < nums.size(); i++) {
priority_queue<int> que_max; // 최대 힙
priority_queue<int, vector<int>, greater<int>> que_min; // 최소 힙
for (int j = i; j < nums.size(); j++) {
que_max.push(nums[j]);
while (que_max.size() - que_min.size() >= 2) {
que_min.push(que_max.top());
que_max.pop();
}
while (que_min.size() && que_max.top() > que_min.top()) {
int a = que_max.top();
que_max.pop();
int b = que_min.top();
que_min.pop();
que_max.push(b);
que_min.push(a);
}
if (i % 2 == j % 2) { // 부분 배열 길이가 홀수인 경우
ret += que_max.top(); // 중앙값 누적
}
}
}
return ret;
}
int main(){
vector<int> v = {2, 4, 6, 3};
cout << solve(v);
}입력
{2, 4, 6, 3}출력
23
동작 원리 요약
핵심 아이디어는 투 포인터 방식으로 시작 지점 i를 고정한 상태에서 끝 지점 j를 하나씩 늘려가며, 두 개의 힙으로 구간 내 값들을 실시간으로 분할 관리하는 것입니다. 새로운 원소가 추가될 때마다 힙 간 균형만 맞춰주면 최대 힙의 루트가 곧 현재 구간의 중앙값이 되므로, 매번 정렬을 수행하지 않고도 중앙값을 O(log n) 시간에 얻을 수 있습니다. 전체 시간 복잡도는 O(n² log n)이며, 모든 홀수 길이 구간의 중앙값을 누적하여 최종 합계를 계산합니다.