[Programmers] #120811 - 중앙값 구하기 [Java][C++][Python]

문제 링크

---

1. 아이디어

정수 배열 array가 주어질 때, 크기 순으로 정렬했을 때 정중앙에 위치하는 값(중앙값)을 구하면 되는 문제다. array의 길이는 항상 홀수이므로, 오름차순 정렬 후 중간 위치의 인덱스에 위치한 값이 바로 중앙값이다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N \log N)$	$O(1)$

($N$ = array의 길이. 공간은 정렬을 제자리에서 수행한 기준이며, 별도 배열을 두지 않았다)

---

3. 코드

풀이 [Java][C++][Python]

import java.util.*;

class Solution {
    public int solution(int[] array) {
        Arrays.sort(array);
        return array[array.length / 2];
    }
}

#include <bits/stdc++.h>
using namespace std;

int solution(vector<int> array) {
    sort(array.begin(), array.end());
    return array[array.size() / 2];
}

def solution(array):
    array.sort()
    return array[len(array) // 2]

---