-
leetcode top interview 150 | Kth Largest Element in an Array | PriorityQueuePS 2023. 9. 12. 09:52
Question
정수배열이 주어질때 k번째로 큰 수를 리턴
Accepted Code - Sorting
import java.util.*; class Solution { public int findKthLargest(int[] nums, int k) { Arrays.sort(nums); int answer = 0; int idx = nums.length - 1; while(k-- > 0){ answer = nums[idx--]; } return answer; } }
정렬을 한번 수행하고 k를 감소시켜가며 배열의 끝에 있는 값을 저장한다.
시간복잡도는 Arrays.sort()로 O(n log n)이 소요된다. Arrays.sort는 이전엔 퀵소트 방식을 사용했지만 Java 7이상부터는 병합정렬과 선택정렬을 활용한 방식으로 변경되었다고 한다.
Accepted Code - PriorityQueue
import java.util.*; class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder()); for(int num : nums){ queue.offer(num); } while(--k > 0){ queue.poll(); } int answer = queue.poll(); return answer; } }
Solve
최대힙을 구성해서 k개수만큼 poll()하고 가장 앞에 있는 값을 poll()해서 리턴해주는 방식이 떠올랐다.
Heap(Binary Heap)
1. 부모노드의 값이 자식보다 크거나 같은 경우면서 완전이진트리인 구조로, 완전이진트리는 마지막 레벨을 제외한 노드들은 전부 채워져있고 마지막 레벨에 있는 노드들은 왼쪽부터 차례대로 채워져있는 트리구조이다.
2. 모든 노드가 자식노드 보다 크거나 같은 구조를 최대힙, 자식노드 보다 작거나 같으면 최소힙 구조라한다.
3. 우선순위가 가장 높은 요소를 삭제하거나 반환하는 연산 시 O(1)의 시간복잡도가 소요된다.최대힙(Max Heap)을 구성하기 위해 우선순위 큐 생성 시 Collections.reverseOrder()로 최대값이 맨 앞으로 유지될 수 있도록 설정해줬다.
nums를 순회하며 모든 값을 큐에 넣어주고 while문을 통해 k번째 전까지 최대값들을 제거하여 큐의 맨 앞에 k번째로 큰 수가 올 수 있도록 한다.
'PS' 카테고리의 다른 글
java 프로그래머스 2018 카카오 블라인드 1차 셔틀버스 풀이 | Map, Queue 활용 (0) 2024.05.31 leetcode top interview 150 | Clone Graph | BFS (0) 2023.09.15 leetcode top interview 150 | Binary Tree Right Side View | DFS (0) 2023.09.06 leetcode top interview 150 | Find Peak Element | Binary Search (0) 2023.09.05 leetcode top interview 150 | Min Stack | ArrayList (0) 2023.09.01