문제 개요
숫자로 이루어진 리스트 nums가 주어졌다고 가정해 보겠습니다. 이 리스트를 크기가 같은 두 부분으로 나누되, 각 부분의 중앙값(median)의 절대 차이가 최소가 되도록 만들고, 그 차이를 구하는 것이 목표입니다. 단, 이 문제에서는 리스트 길이의 절반(len(nums) / 2)이 항상 홀수라는 조건이 주어집니다.
예시
입력이 [2, 10, 8, 5, 4, 7]이라면 결과는 2가 됩니다. 리스트를 [2, 5, 10]과 [4, 7, 8]로 나누면 각각의 중앙값은 5와 7이며, 두 값의 차이는 2이기 때문입니다.
풀이 아이디어
핵심은 정렬에 있습니다. 리스트를 오름차순으로 정렬한 뒤 절반씩 나누면, 앞쪽 절반의 중앙값은 정확히 가운데 바로 앞 원소인 nums[m-1]이 되고, 뒤쪽 절반의 중앙값은 nums[m]이 됩니다. 정렬된 배열에서 이 두 원소는 서로 인접해 있으므로, 어떻게 리스트를 나누더라도 만들 수 있는 중앙값 쌍 중 가장 작은 차이를 가지게 됩니다.
따라서 다음 단계로 문제를 해결할 수 있습니다.
- 리스트
nums를 오름차순으로 정렬합니다. m := len(nums) // 2(리스트 길이의 절반, 몫 연산)|nums[m] - nums[m-1]|을 반환합니다.
정렬 한 번이면 충분하기 때문에 시간 복잡도는 O(n log n)으로 매우 효율적입니다.
구현 예제
class Solution:
def solve(self, nums):
nums.sort()
m = len(nums)//2
return abs(nums[m] - nums[m-1])
ob = Solution()
print(ob.solve([2, 10, 8, 5, 4, 7]))
입력
[2, 10, 8, 5, 4, 7]
출력
2
마무리
이 문제는 언뜻 복잡한 조합 탐색처럼 보이지만, 정렬 후 가운데 인접한 두 원소만 비교하면 답을 바로 구할 수 있는 elegant한 문제입니다. 정렬된 데이터에서 중앙값의 성질을 활용하는 대표적인 알고리즘 훈련 문제이므로, 코딩 테스트 준비 과정에서 꼭 익혀두면 좋습니다.