[프로그래머스]heap-더 맵게
- 직접 짠 풀이
import java.util.*;
class Solution {
public int solution(int[] scoville, int K) {
int answer = 0;
PriorityQueue<Integer> spicier = new PriorityQueue<>();
PriorityQueue<Integer> maxCheck = new PriorityQueue<>(Comparator.reverseOrder());
for(int i=0; i<scoville.length; i++){
spicier.add(scoville[i]);
}
for(int i=0; i<scoville.length; i++){
maxCheck.add(scoville[i]);
}
if(K==0) return 0;
if(maxCheck.isEmpty() || maxCheck.peek()==0){
return -1;
}
int s1=0, s2=0;
while(!spicier.isEmpty() && spicier.peek()<K){
if(spicier.size()==1) return -1;
s1 = spicier.poll();
if(spicier.isEmpty()){
spicier.add(s1*2);
} else {
s2 = spicier.poll();
spicier.add(s1 + s2*2);
}
answer++;
}
return answer;
}
}
java 내장 클래스 PriorityQueue는 heap으로 만들어졌다는 사실을 며칠전에 알고 이를 이용.
직접 짜긴 했는데 정답 코드들 보니 너무 간결.. 나는 예외처리를 하다보니 코드가 너무 더러워졌다. 다시 깔끔하게 짜야지
- 두번째 풀이
import java.util.*;
class Solution {
public int solution(int[] scoville, int K) {
int answer = 0;
PriorityQueue<Integer> spicier = new PriorityQueue<>();
for(int i=0; i<scoville.length; i++){
spicier.add(scoville[i]);
}
while(spicier.size()>1 && spicier.peek()<K){
spicier.add(spicier.poll() + spicier.poll()*2);
answer++;
}
return spicier.peek() >= K? answer : -1;
}
}
예외처리를 깔끔하게 한 풀이.
알고리즘
- 우선순위 큐에 scoville을 담는다.
- 큐의 size가 2이상이고 K 이하인 음식이 남아있을 때 가장 안 매운 음식과 두번째로 안 매운 음식을 합쳐 scoville을 보정한다. 그리고 answer을 increment한다.
- 큐 안에 scoville 지수가 K를 넘지 않는 음식이 존재한다면 -1을 return하고 존재하지 않으면 정상적으로 answer를 return한다.
Author And Source
이 문제에 관하여([프로그래머스]heap-더 맵게), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@snusun/프로그래머스heap-더-맵게저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)