본문 바로가기

Heap

 (8)
[Medium] 378. Kth Smallest Element in a Sorted Matrix (아마존) #문제 설명 378번 문제는 정수 k와 n x n 정사각형 matrix가 주어지고, matrix의 각 칸에는 정수들이 담겨있다. 이 문제에서는 matrix안에서 정수 k번째로 작은 정수들을 전부 return해주면 된다. 예를 들어 [[1,5,9], [10,11,13] , [12,13,15]] 라는 2d 매트릭스가 주어지고 정수 k = 4가 주어지면, matrix안의 4번째로 작은 10을 return해주면 된다. #문제 풀이 class Solution { public int kthSmallest(int[][] matrix, int k) { PriorityQueue maxHeap = new PriorityQueue(Collections.reverseOrder()); for(int i = 0; i < matr..
[Medium] 703. Kth Largest Element in a Stream (아마존 코딩 테스트 기출 문제) #문제 설명 Leetcode 703번문제는 int k 와 정수 array가 주어진다. 또한 이 array는 stream이기때문에 계속 정수들을 array에 추가 시킨다. 이 문제에서는 주어진 array에 여러개의 정수를 add하고, add가 끝난뒤 array에서 k번째로 큰 정수값을 반환시켜주면된다. #문제 풀이 class KthLargest { private PriorityQueue minHeap; private int k; public KthLargest(int k, int[] nums) { minHeap = new PriorityQueue(); this.k = k; for(int i = 0; i < nums.length;i++){ minHeap.add(nums[i]); if(minHeap.size(..
[Lecture 10] Heap / 힙 #Heap 이란 컴퓨터의 기억 장소에서 그 일부분이 프로그램들에 할당되었다가 회수되는 작용이 되풀이되는 영역. 스택 영역은 엄격하게 후입 선출(LIFO) 방식으로 운영되는 데 비해 히프는 프로그램들이 요구하는 블록의 크기나 요구/횟수 순서가 일정한 규칙이 없다는 점이 다르다. 대개 히프의 기억 장소는 지시자(pointer) 변수를 통해 동적으로 할당받고 돌려준다. 이는 연결 목록이나 나무, 그래프 등의 동적인 자료 구조를 만드는 데 꼭 필요한 것이다. 쉽게 말해 여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 이진 트리이다. 짧게 힙(Heap)이라고 줄여서 부른다 영단어 힙(heap)은 '무엇인가를 차곡차곡 쌓아올린 더미'라는 뜻을 지니고 있다. 힙은 항상 완전 이진 트리의 형태를 띠..
[Hard] 295. Find Median from Data Stream (Microsoft 기출 문제) #문제 설명 #문제 풀이 class MedianFinder { PriorityQueue minHeap = new PriorityQueue(); PriorityQueue maxHeap = new PriorityQueue(Collections.reverseOrder()); public MedianFinder() { } public void addNum(int num) { maxHeap.offer(num); minHeap.offer(maxHeap.poll()); if (minHeap.size() > maxHeap.size()) maxHeap.offer(minHeap.poll()); } public double findMedian() { if (maxHeap.size() > minHeap.size()) retu..
[Medium] 451. Sort Characters By Frequency #문제 설명 #문제 풀이 HashMap + Heap class Solution { public String frequencySort(String s) { Map map = new HashMap(); for (char c : s.toCharArray()) { map.put(c, map.getOrDefault(c, 0) + 1); } PriorityQueue pq = new PriorityQueue((a,b) -> map.get(b) - map.get(a)); for (char c : map.keySet()) { pq.offer(c); } StringBuilder sb = new StringBuilder(); while (!pq.isEmpty()) { char c = pq.poll(); for (int i ..
[Medium] 1046. Last Stone Weight (구글 코딩 테스트 기출문제) #문제 설명 #문제 풀이 class Solution { public int lastStoneWeight(int[] stones) { PriorityQueue maxHeap = new PriorityQueue(Collections.reverseOrder()); int sum = 0; for(int i = 0; i 1){ int num1 = 0; int num2 = 0; if(maxHeap.size() >= 2){ num1 = maxHeap.poll(); num2 = maxHeap.poll(); } m..
[Medium] 347. Top K Frequent Elements (애플/MS/메타/아마존) #문제 설명 Leetcode 347번 문제는 array와 정수 k가 주어진다. 배열에서 가장 빈도가 높은 k개의 요소를 return하면된다. 예를 들어 [1,1,1,2,2,3]이 라는 배열에 k=2가 주어지면 1 (빈도 3번) 과 2 (빈도 2번)을 반환해주면 된다. 만약 k=3이라면 1,2,3 모두 반환 해주면 된다 #문제 풀이 class Solution { public int[] topKFrequent(int[] nums, int k) { // O(1) time if (k == nums.length) { return nums; } // 1. build hash map : character and how often it appears // O(N) time Map count = new HashMap()..
[Medium] Kth Largest Element in an Array (아마존/구글) #문제 설명 Leetcode 215번 문제는 정수로 채워진 배열 nums와 정수 k가 주어진다. 주어진 배열안에서 k번째로 큰 정수를 return하면 된다. 위에 예시를 보면 [3,2,1,5,6,4] 의 배열과 k=2가 주어진다 이경우 에는 배열에서 2번째로 큰 숫자를 return하면 되기에 5를 return해야한다. #문제 풀이 Min-heap 풀이: class Solution { public int findKthLargest(int[] nums, int k) { //min-heap PriorityQueue minHeap = new PriorityQueue(); for(int i = 0; i < k;i++){ minHeap.add(nums[i]); } for(int i = k; i < nums.leng..

티스토리툴바