[LeetCode] Kth Largest Element in an Array - Javascript

Kth Largest Element in an Array

[정렬을 하지 않고 k 번째로 큰 수 찾기]

 

제약 조건 

1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

 

Example

ex1) Input: nums = [3,2,1,5,6,4], k = 2
     Output: 5
 

ex2) Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
     Output: 4

문제 접근 방식

정렬을 하지 않고 k 번째로 큰 값을 구하는 문제이다.
해당 문제는 Heapify의 특성을 이용해 문제를 풀이할 수 있다.

Heapify 작업은 마지막 노드의 부모 노드를 루트로 하는 서브 트리를 힙 조건을 만족하도록 조정하는 것이다.
이러한 특성을 이용해 서브 트리의 루트가 되는 노드를 하나씩 앞으로 이동하며 서브 트리를 힙로 하나씩 변경하는 행위를
bubble down이라고 한다.

또한, 해당 구조의 배열에서 왼쪽 자식 노드를 찾고 싶다면 arr[2i+1]을 하면 되고,

오른쪽 자식 노드는 arr[2i+2]를 하면 자식을 찾을 수 있다.

코드 설명은 아래와 같다.

 

맨 처음 배열의 중간 인덱스를 mid에 저장한다.
후에 bubbleDown 함수를 사용하며 배열을 정렬할 건데, 이때 시작점을 중간 인덱스로 시작하는 것이다.
그 후 반복문으로 중간 인덱스부터 시작하여 배열을 힙 구조로 정렬한다.

(현재 배열은 아무런 정렬도 되어있지 않은 무작위 배열이다.)
bubbleDown 함수 내에선, 주어지는 인덱스를 기준으로 힙 특성을 유지하도록 배열을 재정렬한다.

 

위의 특성을 이용해 왼쪽 자식과 오른쪽 자식을 비교하며 가장 큰 값을 가진 자식과 swap 함수를 호출해 교환을 하고,
bubbleDown 함수를 재귀 호출해 반복한다.
이렇게 for 반복문을 나오게 되면, 가장 큰 k의 값을 구하기 위해 while(k--)을 통해 가장 큰 값을 구하는 작업을 하는데,
swap(0, nums.length-1)를 통해 배열의 제일 처음 인덱스와 마지막 인덱스를 교환하면서 가장 큰 인덱스를 가진 배열로 이동시키고
해당 상태가 되었으면 result에 가장 큰 값을 저장한다. 

그 후 bubbleDown(0)을 해주는 이유는 가장 큰 값을 가진 인덱스를 배열 맨 위로 오게 해서 다시 힙 구조를 유지하도록 해주는 것이다.

 

해당 문제를 풀이하기 위해, 혼자서 많은 시간을 고군분투하며 코드를 작성했었다.

뭔가 글로 작성하기 애매한 트러블이 많이 발생 해 이상한곳에서 시간을 많이 쏟기도 했었다.
대략적인 힙 코드는 작성했지만 테스트케이스 전부 통과가 되지 않는 경우가 발생해 다른 풀이를 참고하며,

코드의 구조나 틀린 곳은 조금 수정하여 풀었다..

solve 전체 코드

var findKthLargest = function (nums, k) {
   const mid = Math.floor(nums.length / 2);

   for (let i = mid; i >= 0; i--) {
      bubbleDown(i);
   }

   let result;

   while (k--) {
      swap(0, nums.length - 1);
      result = nums.pop();
      bubbleDown(0);
   }

   function bubbleDown(i) {
      const leftChild = 2 * i + 1;
      const rightChild = 2 * i + 2;
      let max = i;

      if (leftChild < nums.length && nums[leftChild] > nums[max]) {
         max = leftChild;
      }
      if (rightChild < nums.length && nums[rightChild] > nums[max]) {
         max = rightChild;
      }

      if (max !== i) {
         swap(i, max);
         bubbleDown(max);
      }
   }

   function swap(i, j) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
   }

   return result;
};