[Java] 215. Kth Largest Element in an Array

문제 파악

정수 배열 nums 가 주어지고 k가 주어진다.

 

k번째로 큰 원소를 반환하면 된다. 

 

---

풀이

1️⃣ PriorityQueue를 활용한 풀이

💡 떠오른 Idea

내림차순으로 정렬하는 우선순위큐에 원소들을 넣고

k번째의 원소를 반환한다.

 

import java.util.*;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        for (int num : nums) {
            pq.offer(num);
        }

        int ans = 0;
        while (k-- > 0) {
            ans = pq.poll();
        }
        return ans;
    }
}

 

결과

 

---

📖 회고

너무 간단하게 문제가 해결되었다.

 

하지만, 시간 복잡도가 약간 느린 편이라, 더 빠른 시간에 해결한 다른 풀이를 보니 sort 를 이용한 방식이었다.

 

문제에서 sort 없이 푸는 것을 원했으므로 이 방식으로 푸는게 맞는 것 같다.