문제 개요
여러 개의 원소를 가진 배열 A가 주어졌을 때, 기하 평균(geometric mean)이 가장 커지는 부분집합을 찾아야 합니다.
예를 들어 A = [1, 5, 7, 2, 0]이라면, 기하 평균이 가장 큰 부분집합은 [5, 7]이 됩니다.
접근 방식
이 문제는 한 가지 간단한 트릭으로 해결할 수 있습니다. 실제로 기하 평균을 계산할 필요가 없다는 점입니다.
기하 평균은 n개의 수의 곱에 n제곱근을 취한 값인데, 현재 기하 평균보다 작은 값을 새로 추가하면 오히려 기하 평균이 낮아집니다. 따라서 원소를 더 추가하는 것은 도움이 되지 않으며, 배열에서 가장 큰 두 원소가 곧 기하 평균이 최대가 되는 부분집합입니다. 즉, 배열을 한 번만 순회하여 최댓값과 두 번째로 큰 값을 찾아 출력하면 됩니다.
알고리즘 단계
- 배열의 길이가 2보다 작으면 처리 불가 메시지를 출력하고 종료합니다.
- 최댓값(max)과 두 번째 최댓값(second_max)을 각각 INT_MIN으로 초기화합니다.
- 배열을 순회하며 현재 원소가 max보다 크면 second_max에 max를 넣고 max를 갱신하고, 그렇지 않고 second_max보다 크면 second_max를 갱신합니다.
- 순회가 끝나면 두 값을 출력합니다.
예제 코드
#include <iostream>
using namespace std;
void largestGeoMeanSubset(int arr[], int n) {
if (n < 2) {
cout << "원소의 개수가 너무 적습니다";
return;
}
int max = INT_MIN, second_max = INT_MIN;
for (int i = 0; i < n; i++) {
if (arr[i] > max) {
second_max = max;
max = arr[i];
} else if (arr[i] > second_max)
second_max = arr[i];
}
cout << second_max << ", " << max;
}
int main() {
int arr[] = {1, 5, 7, 2, 0};
int n = sizeof(arr)/sizeof(arr[0]);
largestGeoMeanSubset(arr, n);
}실행 결과
5, 7
복잡도 분석
- 시간 복잡도: O(n) — 배열을 한 번만 순회합니다.
- 공간 복잡도: O(1) — 추가적인 저장 공간을 사용하지 않습니다.
기하 평균 계산 시 발생할 수 있는 제곱근 연산이나 오버플로우 문제를 피하면서, 선형 시간 안에 정답을 구할 수 있는 효율적인 방법입니다.