분류 전체보기361 힙을 사용해 K번째로 큰 수 구하기 힙을 사용해서 N개의 정렬되지 않은 데이터에 대해 K번째로 큰 숫자를 구하는 방법을 정리해보겠습니다. 1. MinHeap 사용 1ST. 최초 K개의 숫자에 대해 MinHeap을 구성합니다. (arr[0] ~ arr[k-1]) 2ND. 나머지 (N-1) - K개의 데이터값을 MinHeap의 루트와 비교하며 힙을 갱신합니다. (arr[k] ~ arr[n-1]) 2-1. 현재 데이터가 힙의 루트보다 큰 경우 → 힙 루트값 삭제, 현재 데이터 힙에 추가, 다시 MinHeap 만들기 2-2. 현재 데이터가 힙의 루트보다 작은 경우 → 무시 이렇게 N개의 데이터가 MinHeap의 루트와 비교가 끝나면, 힙의 루트값이 K번째로 큰 수가 됩니다. 그림을 통해 살펴보겠습니다. 시간복잡도는 1. K개의 원소로 MinHea.. 2019. 11. 1. 이전 1 ··· 88 89 90 91 다음
