참고
문제해설
문제 로직고민
NOTE
•
가장 낮은 스코빌 지수를 구하면 되는 문제이므로 최소힙을 사용했다.
PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a1, a2) -> a1.compareTo(a2));
Java
복사
최소힙 구현방법
•
목표치 스코빌을 만들 수 없는 경우와, 스코빌을 한번도 섞지않아도 되는 경우를 나눠야 한다.
◦
while문에서 현재 값이 목표보다 작고, 큐의 크기가 비어있다면 불가능하다 판단한다.
◦
이외에는 cnt++로 카운팅하므로 그대로 return값을 보낸다.
작성코드
NOTE
import java.util.*;
class Solution {
public int solution(int[] scoville, int K) {
PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a1, a2) -> a1.compareTo(a2));
for(int i : scoville){
pq.add(i);
}
int cnt = 0;
while(true){
int cur = pq.poll();
if(cur < K && pq.size() < 1) return -1;
if(cur >= K) break;
cnt++;
if(cur < K){
int curNext = pq.poll();
int mix = cur + curNext*2;
pq.offer(mix);
}
}
return cnt;
}
}
Java
복사
다른사람 풀이
NOTE
import java.util.*;
class Solution {
public int solution(int[] scoville, int K) {
PriorityQueue<Integer> q = new PriorityQueue<>();
for(int i = 0; i < scoville.length; i++)
q.add(scoville[i]);
int count = 0;
while(q.size() > 1 && q.peek() < K){
int weakHot = q.poll();
int secondWeakHot = q.poll();
int mixHot = weakHot + (secondWeakHot * 2);
q.add(mixHot);
count++;
}
if(q.size() <= 1 && q.peek() < K)
count = -1;
return count;
}
}
Java
복사
깔끔한 코드
•
while문 도중이 아니라, q의 크기로 마지막에 변환할 수 있다. (성능은 크게 차이 없을듯)