https://leetcode.com/problems/kth-largest-element-in-an-array/description/
Kth Largest Element in an Array - LeetCode
Can you solve this real interview question? Kth Largest Element in an Array - 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 eleme
leetcode.com
sort를 쓰지 않고 배열의 K번째로 큰 요소를 찾는 문제이다.
알고리즘을 복습하려고 따라가고 있는 리트코드 로드맵상에선 Heap & Priority Queue로 지정되어있어 Priority Queue를 이용해서 풀었다.
사실 PriorityQueue도 sort를 이용하는게 아닌가 하는 의구심이 들기는 한다.
하지만 Arrays.sort()를 이용하여 문제를 풀 경우 오류를 내뱉었다.
문제에서 PriorityQueue를 사용시 오류가 발생하지 않으며 이는 PriorityQueue를 허용한다는 의미이며
그것이 문제의 의도라고 확인하였다.
문제 풀이에 성공한 코드는 아래와 같다.
import java.util.*;
public class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
// PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for (int num : nums) {
pq.add(num);
}
while (k-- > 1) {
pq.poll();
}
return pq.poll();
}
}
PriorityQueue 는 기본적으로 Integer 의 compareTo 메서드에 따라 오름차순으로 정렬하기 때문에 생성시 새로운 compareTo 메서드를 오버라이드 해야한다. Collections.reverseOrder()를 이용해 간단히 역순 정렬을 할 수도 있으며, 직접 수식을 compareTo 메서드에 오버라이드 해주는 것도 방법이다. 이 때 화살표 함수로 손쉽게 메서드를 표기할 수 있다.
PriorityQueue에 nums 배열을 넣은 후에는 간단하다. k번째로 큰수이기 때문에 k번째의 수를 뽑아내주면 된다. k-1 번째까지 뽑은 후 리턴시 k번째 수를 poll하여 반환하였다.