Kth Largest Element in an Array - 리트코드

평가

결과 : 성공
풀이시간 : 12분

아이디어

우선순위 큐를 사용하면 쉽게 해결되는 문제입니다.
자바에서는 PriorityQueue라는 자료구조를 지원해줘 별다른 어려움 없이 문제를 풀었습니다.

PriorityQueue의 파라미터로 Comparator를 넣어줘 어떻게 우선순위를 결정할지 정할 수 있습니다.

Compare 관련 꿀팁

정렬 꿀팁

리턴값이 양수가 나오면 두 값의 위치가 변경된다

compare 등의 메서드에서 리턴 결과가 작으면 작을수록 우선순위가 더 높습니다. 이 말은 우선순위가 높은 애들이 왼쪽으로 이동한다.

Comparator를 만들어야 하는 순간들이 많은데요. 사용할 때마다 식을 세우는 게 너무 헷갈려 저만의 암기공식을 만들었습니다.

public int compare(Integer o1, Integer o2) {
    return o2 - o1;
}

o1을 기준으로 o2를 확인합니다.
만약 o1이 1, o2가 3이라면 o2-o1은 2가 되겠죠? 양수이기 때문에 두 값의 위치가 변경됩니다.
[1,3] -> [3,1]

저는 맨날 헷갈렸던 포인트인데 이 방식을 사용하고 나서 헷갈리지 않게 되었습니다. 부디 도움이 되셨길 바라겠습니다.

정답 코드

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Queue<Integer> queue = new PriorityQueue<>(new Comparator<>() {
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for(int num: nums) {
            queue.offer(num);
        }
        
        int answer = 0;
        for(int i=0; i<k;i++) {
            answer = queue.poll();
        }
        return answer;
    }
}