힙

[PGM_42626] 더 맵게 (Java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/42626# 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 Heap 처음에는 그냥 단순하게 초기 정렬 후 삽입정렬로 값을 계속 넣어주었는데 효율성에서 0점을 받았다. 곰곰히 생각해보니 적절한 자료구조로 Heap을 사용하면 되겠다고 생각되어 Heap을 사용해 문제를 해결해 주었다. 더 맵게 문제는 매운맛에 대한 배열과 매운 강도 K값이 input으로 주어진다. ..

자바에서 Heap 사용하는 방법

Java에서 Heap 사용하기 Java에서는 Collection으로 Heap이 없다. 하지만 Max-Heap과 Min-Heap을 Primary Queue를 활용하여 구현할 수 있다. 이번 시간에는 Primary Queue를 활용해 Heap을 구현하는 방법을 알아보고자 한다. Heap이라는 자료구조는 값들이 모여있는 자료구조를 트리로 구현하였다고 할 때, 루트에 위치하는 값이 최대 혹은 최소값이 되는 자료구조를 의미한다. 최소 힙 사용하기 최소힙을 사용하는 것은 Primary Queue를 그대로 사용해주면 된다. PriorityQueue minHeap = new PriorityQueue(); 이렇게 사용하여 컬렉션에 데이터를 넣으면 remove되는 peek의 값이 minHeap의 최소값이 된다. Prim..