알고리즘 풀이

0n1dev · 0n1dev · commit 96adba5484aa · 2021-04-10T21:37:35.000+09:00
diff --git a/Heap/Heap1.java b/Heap/Heap1.java
@@ -0,0 +1,35 @@
+import java.util.*;
+
+class Solution {
+    public int solution(int[] scoville, int K) {
+        int answer = -1;
+        int idx = 0;
+        int s1 = 0, s2 = 0;
+        int temp;
+
+        PriorityQueue<Integer> q = new PriorityQueue<Integer>(scoville.length);
+
+        for (int e : scoville) {
+            q.offer(e);
+        }
+
+        while (q.size() > 1) {
+            if (q.peek() >= K) {
+                answer = idx;
+                break;
+            }
+
+            s1 = q.poll();
+            s2 = q.poll();
+            temp = s1 + (s2 * 2);
+            q.offer(temp);
+            idx++;
+        }
+
+        if (q.poll() >= K) {
+            answer = idx;
+        }
+
+        return answer;
+    }
+}
diff --git a/Heap/Heap2.java b/Heap/Heap2.java
@@ -0,0 +1,21 @@
+class Solution {
+    public int[] topKFrequent(int[] nums, int k) {
+        HashMap<Integer, Integer> m = new HashMap<Integer, Integer>(nums.length);
+
+        for (int num : nums) {
+            m.put(num, m.getOrDefault(num, 0) + 1);
+        }
+        
+        List<Integer> list = m.entrySet().stream()
+                .sorted(Collections.reverseOrder(Map.Entry.comparingByValue()))
+                .map(Map.Entry::getKey).collect(Collectors.toList());
+        
+        int[] result = new int[k];
+        
+        for (int i = 0; i < k; i++) {
+            result[i] = list.get(i);
+        }
+        
+        return result;
+    }
+}
diff --git a/Heap/ReadMe.md b/Heap/ReadMe.md
@@ -0,0 +1,18 @@
+# Heap
+---
+
+- **완전 이진 트리 일종** 우선 순위 큐를 위하여 만들어진 자료구조
+- 여러 개의 값들 중 최댓 값 or 최솟 값을 빠르게 찾아 내기 위한 자료구조
+- **반 정렬 상태(느슨한 정렬 상태)**
+
+## Heap 종류
+---
+
+- 최대 힙
+    - 부모 노드 >= 자식 노드
+    - Java에서 PriorityQueue<E>();
+- 최소 힙
+    - 부모 노드 <= 자식 노드
+    - Java에서 PriorityQueue<Integer>(Collections.reverseOrder());
+
+-> 자바에서 우선순위 큐를 이용하면 쉽게 구현 할 수 있다.
diff --git a/ReadMe.md b/ReadMe.md
@@ -34,10 +34,17 @@
     - leetcode 21
     - leetcode 148
 
-# 4주차 자료구조와 알고리즘
+# 5주차 자료구조와 알고리즘
+---
+
+- [힙](./Heap)
+    - leetcode 347
+    - Programmers 더 맵게
+
+# 6주차 자료구조와 알고리즘
 ---
 
 - [트리](./Tree)
     - leetcode 104
-    - leetcode 203
+    - leetcode 230
     - leetcode 617
