[프로그래머스][Java] lv2 더 맵게 (Heap) - 문제풀이 및 팁

https://programmers.co.kr/learn/courses/30/lessons/42626?language=java 

코딩테스트 연습 - 더 맵게

문제요약

여러 음식의 스코빌 지수가 주어진 배열이 주어지며, 가장 낮은 스코빌 두개 음식을 섞어 스코빌을 높일 수 있다.

모듬 음식의 스코빌 지수를 K이상으로 만들려면 몇 번 섞어야하는지를 구하기.

 

풀이

스코빌 지수가 가장 낮은 두개의 음식을 골라야 한다는 부분에서 배열 정렬을 먼저 생각할 수 있지만, 섞은 음식을 다시 배열에 넣으면 순서가 또 다시 달라진다. 그 방식으로 접근하면 복잡도가 올라갈 것 같다는 예상을 했다.

 

1. 배열의 음식을 우선순위 큐에 담는다.

2. 큐의 스코빌이 K가 넘는지를 체크하며 순회한다.

3. K 미만이라면, 두 음식을 큐에서 꺼내 섞고 넣어준다.

 

소스코드

https://github.com/999inim/Algorithm/blob/main/programmers/PS51.java

---

API정리 및 팁

1. PriorityQueue

우선순위 큐에서 값을 꺼내면 우선순위가 높은 값을 꺼낸다. 

(**정수타입 우선순위 큐는 값이 작은게 우선순위가 높다.)

따라서, 값을 꺼내면 큐의 요소 중 제일 작은 값부터 나온다.

---

2. while문

!queue.isEmpty()

큐가 비어 있지 않으면, 계속 반복문을 수행

---

느낀점

- 100% 확실한 코드가 어디까지인지 마일스톤을 머릿속으로 남기면서 구현하기.