[프로그래머스 입문 / 파이썬] 중앙값 구하기

실습코드 :

https://colab.research.google.com/drive/1OsGiouhwUTKc1IhEYr-ycGH9BVxkfwEy?usp=sharing

[프로그래머스 입문 / 파이썬] 중앙값 구하기.ipynb

Colab notebook

colab.research.google.com

문제 설명

중앙값은 어떤 주어진 값들을 크기의 순서대로 정렬했을 때 가장 중앙에 위치하는 값을 의미합니다. 예를 들어 1, 2, 7, 10, 11의 중앙값은 7입니다. 정수 배열 array가 매개변수로 주어질 때, 중앙값을 return 하도록 solution 함수를 완성하세요.

제한사항

array의 길이는 홀수입니다.
0 < array의 길이 < 100
-1,000 < array의 원소 < 1,000

입력과 출력 예

array	result
[1, 2, 7, 10, 11]	7
[9, -1, 0]	0

입력 예 설명

입력 예 #1: [1, 2, 7, 10, 11] -> 7
입력 예 #2: [9, -1, 0] -> 0

풀이 계획

중앙값을 구하는 방법은 다음과 같습니다:

배열을 오름차순으로 정렬합니다.
정렬된 배열에서 중앙값을 찾습니다. 배열의 길이가 홀수이므로, 배열의 길이를 2로 나눈 몫에 해당하는 인덱스가 중앙값이 됩니다.

코드 구현

def solution(array):
    # 배열을 오름차순으로 정렬합니다.
    array.sort()
    # 중앙값의 인덱스를 계산합니다.
    mid_index = len(array) // 2
    # 중앙값을 반환합니다.
    return array[mid_index]

# 예시 테스트
print(solution([1, 2, 7, 10, 11]))  # 출력: 7
print(solution([9, -1, 0]))        # 출력: 0

풀이 방법 2: 분할 정복 사용

분할 정복 알고리즘을 사용하여 중앙값을 찾을 수 있습니다. 이 방법은 배열을 두 부분으로 나누고, 중앙값이 포함된 부분을 계속해서 분할하여 찾습니다.

def quickselect(arr, k):
    if len(arr) == 1:
        return arr[0]

    pivot = arr[len(arr) // 2]
    lows = [el for el in arr if el < pivot]
    highs = [el for el in arr if el > pivot]
    pivots = [el for el in arr if el == pivot]

    if k < len(lows):
        return quickselect(lows, k)
    elif k < len(lows) + len(pivots):
        return pivots[0]
    else:
        return quickselect(highs, k - len(lows) - len(pivots))

def solution(array):
    return quickselect(array, len(array) // 2)

# 예시 테스트
print(solution([1, 2, 7, 10, 11]))  # 출력: 7
print(solution([9, -1, 0]))        # 출력: 0

풀이 방법 3: 힙 자료구조 사용

힙 자료구조를 사용하여 중앙값을 효율적으로 찾을 수 있습니다. 최대 힙과 최소 힙을 사용하여 중앙값을 찾습니다.

import heapq

def solution(array):
    min_heap = []
    max_heap = []

    for num in array:
        heapq.heappush(max_heap, -heapq.heappushpop(min_heap, num))
        if len(max_heap) > len(min_heap):
            heapq.heappush(min_heap, -heapq.heappop(max_heap))

    return min_heap[0]

# 예시 테스트
print(solution([1, 2, 7, 10, 11]))  # 출력: 7
print(solution([9, -1, 0]))        # 출력: 0

시간 복잡도 비교

첫 번째 방법 (정렬): O(n log n) - 정렬을 사용하므로
두 번째 방법 (분할 정복): O(n) 평균 시간 복잡도
세 번째 방법 (힙): O(n log n) - 힙을 사용하는 삽입 및 삭제 연산