리트코드 - 215. Kth Largest Element in an Array

리트코드 -  215. Kth Largest Element in an Array

출처 - https://leetcode.com/problems/kth-largest-element-in-an-array/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

주어진 정수 배열 nums와 정수 k에 대해, 배열에서 k번째로 큰 요소를 반환합니다. 이는 정렬된 순서에서 k번째로 큰 요소를 의미하며, 중복되는 요소를 고려해야 합니다. 정렬하지 않고 이 문제를 해결할 수 있는지 확인할 수 있나요?

 

의사코드

우선순위 큐 생성 (역순) 큐에 nums 배열의 num값 입력 answer = 0 반복문 시작 ( k > 1 일때까지)     answer = 큐의 poll 값     k-- 반복문 종료 answer 리턴

 

풀이코드

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue(Collections.reverseOrder());
        for (int num : nums) {
            pq.add(num);
        }
		int answer = 0;
        while (k > 0) {
            answer = pq.poll();
            k--;
        }
        return answer;
    }
}

 

코드설명

힙 자료구조를 기반으로 하는 우선순위 큐를 이용하였다.

생성자에 Collections.reverseOrder()를 적용하면 내림차순으로 적용이 된다.

 

각각 숫자를 큐에 넣어서 내림차순으로 정렬을 하고, 하나씩 꺼내게되면 원하는 값을 얻을 수 있다.

 

시간복잡도 - O(n * logn)

공간복잡도 - O(n)

 

문제를 풀며 생각한 흐름과 배운 점

배열의 정렬을 이용하지 않고 우선순위 큐의 정렬 기능을 이용하였다.

사실 이럴거면 배열의 일반 정렬을 이용하는 것이 나은 것 같다.

 

다른 코드

class Solution {
    public int findKthLargest(int[] nums, int k) {
        List<Integer> list = new ArrayList<>();
        for (int num: nums) {
            list.add(num);
        }
        
        return quickSelect(list, k);
    }
    
    public int quickSelect(List<Integer> nums, int k) {
        int pivotIndex = nums.size() / 2;
        int pivot = nums.get(pivotIndex);
        
        List<Integer> left = new ArrayList<>();
        List<Integer> mid = new ArrayList<>();
        List<Integer> right = new ArrayList<>();
        
        for (int num: nums) {
            if (num > pivot) {
                left.add(num);
            } else if (num < pivot) {
                right.add(num);
            } else {
                mid.add(num);
            }
        }
        
        if (k <= left.size()) {
            return quickSelect(left, k);
        }
        
        if (left.size() + mid.size() < k) {
            return quickSelect(right, k - left.size() - mid.size());
        }
        
        return pivot;
    }
}

퀵 정렬을 이용하여서 해결한 코드이다.

pivot 값을 정하여, left, mid, right 리스트를 만들어 pivot과 값을 비교하여 각각 left, mid, right에 넣고 있다.

 

left 리스트에는 pivot보다 큰 값들이 들어있고, 만약 k보다 left 리스트 크기가 크면 다시 퀵정렬을 하고 있다.

이렇게 정렬하면 pivot 값이 k값을 가리키게 되고, 값을 리턴한다.

 

정리

우선순위 큐의 정렬 방법과 퀵 정렬 사용방법 익히기