[Programmers] 코딩테스트입문 > 중앙값 구하기

 

이번엔 정렬도 써야하는거 같네 오름차순 정렬은 sort() 니까

정렬을 먼저하고 길이를 구하고 몫을구하면 중앙값이 나오지않을까? 

 

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

 

성능 및 고려 사항

 

• 시간 복잡도: sort() 함수는 Timsort 알고리즘을 사용하며, 평균 및 최악의 경우 시간 복잡도는 **O(n log n)**입니다. 배열에서 중앙값을 찾는 작업은 **O(1)**이므로, 전체 시간 복잡도는 **O(n log n)**입니다.
• 메모리 사용: array.sort()는 제자리 정렬이므로 추가 메모리 사용이 없습니다.

https://d2.naver.com/helloworld/0315536

https://questionet.tistory.com/61

파이썬의 정렬 알고리즘 Timsort (삽입정렬 + 병합정렬)

 

 

 

지금은 제한사항으로 길이가 홀수라고 주어졌지만 만약에 짝수라면 어떻게 될까??

고민해봐야징

 

def solution(array):
    array.sort()
    n = len(array)
    if n % 2 == 1:  # 홀수 길이일 경우
        return array[n // 2]
    else:  # 짝수 길이일 경우
        return (array[n // 2 - 1] + array[n // 2]) / 2

 

뭔가 더 복잡해지긴하는데 길이가 홀수일수만은 없으니..ㅎㅎ