반응형
문제 자체가 힙을 구현하는 카테고리에 있는 걸 보고 접근한 거라, priorityqueue로 풀 수 있다는 걸 알고 풀어서 쉽게 풀어버린 케이스이다. 그래도 오랜만에 heap을 다루는 것이기도 하고, java에 있는 pq를 쓰는 건 처음이라 메소드도 익힐 수 있었다.
💡 Min Heap (PriorityQueue)
Heap?
- 완전 이진 트리의 일종, 우선순위 큐를 위하여 만들어진 자료구조.
- 힙에서는 중복된 값을 허용.
- max heap은 가장 큰 값이 부모노드에, min heap은 가장 작은 값이 부모노드에 있다.
- 부모노드는 자식노드보다 크거나 같고(max heap), 작거나 같아야(min heap) 한다.
- 힙은 배열을 통해 구현할 수 있다.
- 구현을 쉽게 하기 위해 0번 인덱스는 사용하지 않는다.
- 루트 노드가 1번 인덱스이다.
- 왼쪽 자식 노드 인덱스 : (부모노드 인덱스)*2
- 오른쪽 자식 노드 인덱스 : (부모노드 인덱스)*2+1
- 부모 노드 인덱스 : (자식노드 인덱스)/2
자바에서 힙은 java.util에 있는 PriorityQueue를 사용할 수 있고, 기본적으로 min heap을 구현한다.
💡 java.util.PriorityQueue
- 기본적으로 mean heap을 구현한다.
- 요소 삽입 : offer()
- 가장 작은 요소 반환 및 삭제 : poll()
- 가장 작은 요소 반환 : peek()
- 힙의 크기 반환 : size()
이 정도로 정리해 두면 문제는 충분히 풀 수 있다.
문제
매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.
Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.
모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
모든 음식의 스코빌 지수가 K이상이 된다는 것은, min heap에서 가장 우선 순위에 있는 노드의 값이 K이상인 것과 같고, 그렇게 되면 그 아래 모든 노드는 K이상이 되기 때문에, min heap을 이용해서 아주 쉽게 이 문제를 해결할 수 있다.
알고리즘은 다음과 같다.
- PriorityQueue 객체를 Integer 타입으로 생성한다.
- 스코빌 배열에 있는 모든 값을 우선순위 큐에 삽입한다.
- while문을 통해 다음의 조건을 만족하는 경우에만 반복실행한다
"우선순위 큐의 가장 작은 값=가장 먼저 나오는 값이 K보다 작고, 우선순위 큐에 있는 요소가 2개이상인 경우"
다음을 실행한다
우선순위 큐에서 가장 작은 값 두개 꺼내고 위의 식을 통해 섞은 음식의 스코빌 지수를 구한 후 이를 다시 큐에 삽입한다. 그리고 answer 값을 1 올린다.
위 과정을 조건을 만족할 경우에 반복한다 - 위 과정을 마치고 나면 큐는 스코빌 지수가 모두 K이상이거나, 큐에 있는 요소가 2개 미만인 상태일 수 있다.
- 전자의 경우라면 answer를 그대로 반환하면 되고, 후자의 경우라면 모든 음식을 섞어도 K이상이 안된다는 것이므로 문제에서 주어진 조건에 따라 -1을 반환하면 된다.
전체 코드는 아래와 같다.
import java.util.PriorityQueue;
class Solution {
public int solution(int[] scoville, int K) {
int answer = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int item : scoville){
pq.offer(item);
}
while(pq.peek()<K && pq.size()>=2){
int temp1 = pq.poll();
int temp2 = pq.poll();
pq.offer(temp1+(temp2*2));
answer++;
}
if(pq.size()==1 && pq.peek()<K) return -1;
return answer;
}
}
*** while문을 실행하고 나면 어차피 pq.peek()<K라는 것은 pq.size()==1인 것과 동시에 일어나기 때문에, 마지막 if문에서는 pq.peek()K만 만족하면 -1을 반환하도록 코드를 줄여도 된다.
반응형
'CO-TE > 프로그래머스' 카테고리의 다른 글
[프로그래머스] JAVA LV3 "여행경로" 풀이 / DFS+BFS 사용 (0) | 2023.10.24 |
---|---|
[프로그래머스] JAVA LV3 "단어 변환" 풀이 / DFS 사용 (0) | 2023.10.24 |
[프로그래머스] JAVA LV2 "소수 찾기" 풀이 방법 / set 자료구조 사용 (0) | 2023.10.20 |
[프로그래머스] JAVA LV2 "올바른 괄호" 풀이방법 / 스택 사용 (1) | 2023.10.19 |
[프로그래머스] JAVA LV2 "가장 큰 수" 풀이 방법 / Arrays.sort / 람다식 사용 (1) | 2023.10.19 |