2696파이썬1 [python]2696_중앙값 구하기 1 사용한 자료구조 및 개념 : heap 💡 문제풀이 아이디어 및 어려웠던 점 💫 아이디어 1️⃣ heap을 사용하여 중앙값을 구한다. 2️⃣ max_heap에는 중앙값을 포함한 왼쪽 부분을 저장하고, min_heap에는 오른쪽 부분을 저장한다. 3️⃣ 배열은 0번부터 시작이니 짝수번째에서 중앙값을 구한다. 4️⃣ (배열의)짝수번째일 때, 숫자가 min_heap의 최솟값보다 크다면 min_heap에 추가하고, 작다면 max_heap에 추가한다. min_heap에 추가했다면 max_heap에서 숫자 하나를 pop하여 min_heap에 추가한다. → 이때, 중앙값은 정렬한 수열에서 항상 가운데 있다. 따라서 중앙값을 효율적으로 찾기 위해 max_heap의 크기는 min_heap의 크기보다 1만큼 크거나 같아.. 2023. 8. 23. 이전 1 다음
