215. Kth Largest Element in an Array

(24.10.10)
문제를 먼저 파악해보자. 입력된 배열 중 k번째로 큰 원소를 리턴하면 된다.

    public int findKthLargest(int[] nums, int k) {
        return Arrays.stream(nums)
                .sorted()
                .toArray()[nums.length-k];
    }

간단히 해결하긴 했지만 문제의 맨 마지막에 아래와 같이 적혀있었다.

Can you solve it without sorting?

문제의 분류가 Heap/Priority Queue인 것을 보아 insert만 해도 정렬이 되게끔 하는 Collection을 사용하라는 듯 하다.

자바 API에 PriorityQueue가 있어 add한다음 일정 횟수만큼 poll하여 작성해보았다.

public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue=new PriorityQueue<>();
        for (int num : nums)
            queue.add(num);
        for(int i=0; i<nums.length-k; i++)
            queue.poll();
        return queue.poll();
    }