leetcode 215. Kth Largest Element in an Array 배열의 K번째 큰 요소, Python, javascript 풀이

Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
Can you solve it without sorting?

 

정수 배열 수와 정수 k가 주어지면 배열에서 k번째로 큰 원소를 반환합니다.
정렬된 순서에서 k번째로 큰 원소이지 k번째로 구별되는 원소는 아닙니다.
정렬하지 않고 해결

문제 설명

- 정렬하지 않고 k번째의 높은수를 출력하면 되는 문제이다. 힙 활용

 

 

python

class Solution(object):
    def findKthLargest(self, nums, k):
        heap = list()
        # 음수로 변환하여 최대 힙으로 사용
        for num in nums:
            heapq.heappush(heap, -num)

        # k번 만큼 for문을 돌면서 k - 1번째까지 pop
        for _ in range(1, k):
            heapq.heappop(heap)
        
        # 출력 -num을 push 했기 때문에 -heapq로 pop
        return -heapq.heappop(heap)

- 여기서 list를 만들어주고 heapq를 사용해서 음수로 변환하여 push를 해준다.

* heapq는 최소힙이기 때문에 음수로 변환

- 넣은 순서대로 k - 1 번만큼 pop

- 마지막 pop을 통해서 값 출력

- python에서는 이렇게 heapq 모듈을 통해서 간단하게 힙을 구현할 수 있어서 편하다. 

 

---

javascript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    class Heap {
        constructor(size) {
            this.size = size;
            this.heap = new Array(size).fill(0);
            this.count = 0;
        }

        push(data) {
        // 1번 INDEX 데이터 추가
            this.heap[++this.count] = data;

            // 자식과 부모에 대해 설정
            let current = this.count;
            let parent = Math.floor(current / 2);

            /**
            * 자식 노드 / 2 === 부모노드
            * 현재 노드 * 2 === 왼쪽 자식 노드
            * 현재 노드 * 2 + 1 === 오른쪽 자식 노드
            */

            // 현재 위치보다 부모가 더 작은 값이면 -> 최대 힙의 정의에 따라 SWAP
            // 늘 최대 힙은 서브트리에서 부모가 자식노드보다 크거나 같아야한다.
            while (current > 1 && this.heap[current] > this.heap[parent]) {
                [this.heap[current], this.heap[parent]] = [
                    this.heap[parent],
                    this.heap[current],
                ];
            	current = parent;
            	parent = Math.floor(current / 2);
            }
        }

        pop() {
            // 만약 값이 없다면 null
            if (this.count === 0) {
                return null;
            }

            // 첫번째 값이 최대 값
            const data = this.heap[1];

            // 힙의 가장 마지막 값을 루트로 가져옴
            this.heap[1] = this.heap[this.count--];

            let current = 1;
            let child;

            while (1) {
                child = current * 2;

                // 현재 자식중 더 큰값으로 이동
                if (child < this.count && this.heap[child] < this.heap[child + 1]) {
                    child++;
                }

                // SWAP 멈춤 => 자식노드가 마지막까지 왔을때, 부모노드(현재노드)가 자식보다 큰 경우
                if (child > this.count || this.heap[current] > this.heap[child]) break;

                [this.heap[current], this.heap[child]] = [
                    this.heap[child],
                    this.heap[current],
                ];

                current = child;
            }
            return data;
        }
    }

    const maxHeap = new Heap(k);
    let res;

    nums.forEach(num => maxHeap.push(num));

    for (let i = 0; i < k; i++) {
        res = maxHeap.pop();
    }

    return res

};

- 자바스크립트를 통해서 실제 heap을 구현

- 클래스를 통해서 push, pop을 구현하고 결과값을 따로 인스턴스를 통해서 출력

---

 

* 파이썬으로도 어떻게보면 모듈을 사용하지 않고 구현할 수 있지만 모듈을 사용한다면 자바스크립트로 코드를 진행하는것보다 더 빠른 코드 작성이 가능할 것 같긴하다.. 프론트엔드 개발자인데 파이썬으로 코테준비를 하는게 맞는걸까 라는생각이 계속 들지만..

이렇게 파이썬으로 처음 문제를 풀고 코드 풀이를 진행하면서 자바스크립트로 다시 진행하며 익히는 연습들을 해봐야겠다.