이 문제에서는 n개의 정수로 이루어진 배열이 주어지며, 여기에 K개의 요소를 추가한 뒤 결과 배열의 중앙값(median)을 찾아야 합니다. 단, N + k는 홀수라는 조건이 주어집니다.
예시를 통해 문제를 살펴보겠습니다.
입력 −
array = {23, 65, 76, 67} ; k = 1출력 −
67
문제 해결 접근 방법
이 문제를 해결하기 위해 먼저 주어진 배열을 오름차순으로 정렬합니다. 그런 다음 K개의 요소를 배열의 끝에 추가한다고 가정합니다. 즉, 기존 요소보다 큰 값들을 추가하는 것입니다.
N + k가 홀수라는 조건이 주어졌으므로, 중앙값은 다음 공식을 사용해 계산할 수 있습니다.
중앙값 = arr[(n + k) / 2]
예제 코드
다음은 K개의 요소 추가 후 중앙값을 찾는 프로그램입니다.
#include <bits/stdc++.h>
using namespace std;
int findMedianAfterK(int arr[], int n, int K) {
sort(arr, arr + n);
return arr[((n + K)/2)];
}
int main() {
int array[] = {3,56, 8, 12, 67, 10 };
int k = 3;
int n = sizeof(array) / sizeof(array[0]);
cout<<"The median after adding "<<k<<" elements is "<<findMedianAfterK(array, n, k);
return 0;
}출력 결과
The median after adding 3 elements is 56
코드 설명
위 코드의 동작 과정은 다음과 같습니다.
1. findMedianAfterK 함수는 먼저 sort() 함수를 사용해 배열을 오름차순으로 정렬합니다.
2. 정렬된 배열에서 인덱스 (n + K) / 2 위치의 값을 반환합니다. N + k가 홀수이므로 이 위치가 곧 중앙값이 됩니다.
3. 예제에서 배열 {3, 56, 8, 12, 67, 10}을 정렬하면 {3, 8, 10, 12, 56, 67}이 되고, n = 6, k = 3이므로 인덱스 (6+3)/2 = 4 위치의 값인 56이 중앙값으로 출력됩니다.
이 알고리즘의 시간 복잡도는 정렬에 의해 결정되며, O(n log n)입니다.