Java/알고리즘
[자바 알고리즘 인터뷰] ch 10. 데크, 우선순위 큐 (4) - 더 맵게
쥬크버그
2024. 5. 11. 21:49
https://school.programmers.co.kr/learn/courses/30/lessons/42626
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
풀이 1) 우선순위 큐
- '가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수*2)'로 나온 새로운 음식을 다시 추가하고 반복하면서, 스코빌 지수가 K 이상일 때 반복 횟수를 출력하는 것이다.
- 가장 맵지 않은 음식을 계속해서 추출해야 한다는 점에서 우선순위큐를 활용
import java.util.*;
class Solution {
public int solution(int[] scoville, int K) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
// 차례대로 추출하기 위해 우선순위 큐에 모두 삽입
for(int s : scoville) {
pq.add(s);
}
int answer = 0; // 처음에는 섞지 않았으므로 0으로 초기화
// 모든 음식의 스코빌 지수가 K 이상인지 검사
while(pq.peek() < K) {
// 음식이 하나만 남았는데도 K 이상이 아니면 불가능한 경우이므로 -1 반환
if (pq.size() == 1) {
return -1;
}
// 두 음식을 섞어서 새로운 음식을 만들어 삽입
pq.add(pq.poll() + (pq.poll() * 2));
answer++; // 실제로 섞은 횟수를 증가시킴
}
return answer;
}
}