프로그래머스 더 맵게 자바(java) 풀이
문제 정리
- 모든 음식의 스코빌 지수를 K 이상으로 만드려고 한다.
- 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만든다.
- 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
- 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞는다.
- 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 구하여라.
- 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우 -1을 return 하여라.
힙, 우선순위 큐
이는 힙(Heap)을 이용하여 풀 수 있습니다. 그 중에서도 힙을 이용해 구현된 우선수위 큐(Priority Queue) 입니다.
물론 배열이나 연결 리스트를 이용해서 구현할 수도 있지만 일반적으로 힙을 많이 이용합니다.
우선순위 큐도 일반 큐와 마찬가지로 선입선출(FIFO)입니다. 하지만 다른점은 Tree형태(완전 이진트리)라는 것입니다.
또한 가장 우선순위가 높은 자료가 가장 먼출 선출됩니다!!
이진트리 형태로 최대 힙(Max Heap)을 이용하여 구현합니다.
- 최대힙이란?? 부모 노드가 자식노드 보다 값이 큰 완전 이진트리를 이야기 합니다.
우선순위 큐를 이용해서 숫자가 오름차순으로 정렬된 상태로 계속 둘 수 있습니다. 트리 형태기 때문에 검색의 시간복잡도 또한 낮습니다.
문제 풀이
이미 구현된 우선순위 큐를 사용합니다. 다음과 같이 생성할 수 있습니다.
PriorityQueue<Integer> q = new PriorityQueue<>();
PriorityQueue<Person> q2 = new PriorityQueue<>();
저희가 직접 정의한 class를 이용할 수도 있습니다. 이 경우에는 comparator를 작성해 우선순위를 직접 정의해주시면 됩니다!!
while문에서 제일 앞의 원소와 그 다음 원소를 빼고 계산식을 통해 큐에 다시 넣는 과정을 반복합니다. 한 번 반복할때마다 cnt를 증가시킵니다.
- 큐에 2개 이상의 원소가 남아있는 경우에만 합칠 수 있으므로 큐의 크기가 1보다 큰 동안 반복합니다.
- 큐의 맨 앞의 원소가 K 이상이면 나머지 원소도 K 이상이기 때문에 맨 앞의 원소가 K 보다 작으면 계속 섞어야 하기 때문에 그 동안 반복합니다.
큐에 한개만 남아서 빠져나왔을 수 있습니다. 예를들어 입력이 {0,0,0}, 7 인경우 계산 후 큐에는 0만 남아있습니다. 이 경우 K 이상으로 만들 수 없으므로 -1로 출력합니다.
프로그래머스 더 맵게 자바 코드
import java.util.*;
class Solution {
public static void main(String[] args) {
int[] scoville = {0,0,0};
int K = 7;
System.out.println(solution(scoville, K));
}
public static int solution(int[] scoville, int K) {
int cnt = 0;
// 우선순위 큐 생성해서 값 집어 넣기
PriorityQueue<Integer> q = new PriorityQueue<>();
for(int i=0; i<scoville.length; i++)
q.offer(scoville[i]);
// queue에 2개 이상이 남아있는 경우만 합칠 수 있음 -> 마지막 두개 합쳐서 K이상이 될 수도 있음
// queue 맨 앞의 원소가 K 이상이면 나머지 원소도 K 이상임
while(q.size() > 1 && q.peek() < K){
int first = q.poll();
int second = q.poll();
q.offer(first + second*2);
cnt++;
}
// {0,0,0}, 7 인 경우 queue에 남아 있는 마지막 수가 K보다 작은 경우
// 반복해서 K이상으로 만들 수 없는 경우임 => -1 return
if(q.peek() < K)
cnt = -1;
return cnt;
}
}