[코딩테스트] HackerRank - Find the Median

주어진 숫자 배열을 정렬하고 중간 값을 찾습니다.

예시

입력 배열: arr = [5,3,1,2,4]

정렬된 배열: arr = [1,2,3,4,5] 중간값은 3 입니다

배열 크기 n은 홀수 입니다

해결 방법

★ 퀵 셀렉트 알고리즘이 중요한 방법

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

// 배열을 분할하여 k번째 작은 값을 찾는 함수
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // 피벗은 배열의 마지막 값
    int i = low;

    for (int j = low; j < high; ++j) {
        if (arr[j] < pivot) {
            swap(arr[i], arr[j]);
            ++i;
        }
    }
    swap(arr[i], arr[high]); // 피벗을 적절한 위치로 이동
    return i;
}

// 퀵 셀렉트 알고리즘으로 k번째 작은 값 찾기
int quickSelect(vector<int>& arr, int low, int high, int k) {
    if (low == high) {
        return arr[low];
    }

    int pivotIndex = partition(arr, low, high);

    if (k == pivotIndex) {
        return arr[k]; // k번째 작은 값이 피벗과 같을 경우 반환
    } else if (k < pivotIndex) {
        return quickSelect(arr, low, pivotIndex - 1, k); // 왼쪽 부분 배열 탐색
    } else {
        return quickSelect(arr, pivotIndex + 1, high, k); // 오른쪽 부분 배열 탐색
    }
}

// 중간값을 찾는 함수
int findMedian(vector<int> arr) {
    int n = arr.size();
    return quickSelect(arr, 0, n - 1, n / 2);
}

int main() {
    vector<int> arr = {0, 1, 2, 4, 6, 5, 3};
    
    int median = findMedian(arr);
    cout << "Median: " << median << endl;

    return 0;
}