오늘은 프로그래머스의 더 맵게라는 문제를 풀어보았다.
문제 설명은 다음과 같다.
문제 설명
매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.
제한 사항
- scoville의 길이는 2 이상 1,000,000 이하입니다.
- K는 0 이상 1,000,000,000 이하입니다.
- scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
- 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.
문제를 보고 java의 priority queue를 사용하여 풀면 되겠다고 생각했다.
제일 안 매운 음식의 스코빌 지수 더하기 두 번째로 안 매운 스코빌 지수의 두배를 하면 되니까 값이 들어오고 빠질 때마다 정렬이 되는 priority queue를 사용하여 값을 두개 빼주고 계산하여 넣어주고를 반복하면 될 것 같았고 제출을 했더니 정답이 나오게 되었다.
문제 풀이 코드는 다음과 같다.
import java.util.PriorityQueue;
class Solution {
public int solution(int[] scoville, int K) {
int answer = 0;
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int i = 0; i < scoville.length; i++) {
heap.add(scoville[i]);
}
while (heap.peek() < K && heap.size() > 1) {
int min1 = heap.poll();
int min2 = heap.poll();
heap.add(min1 + min2 * 2);
answer++;
}
if (heap.peek() < K) {
return -1;
}
return answer;
}
}우선 처음으로 priority queue를 생성해주고 스코빌 지수의 배열을 넣어준다.
반복문 시작시 조건을 queue의 맨 앞의 값을 보고 K보다 작으면 반복을 돌리고 queue의 크기가 1 이하일 때 멈추게 된다.
반복문 안에서는 값을 두개 빼주고 계산해준뒤 queue에 넣어주고 answer를 증가시켜준다.
위에서 queue의 크기가 1이하일 때 멈추는 이유는 계산을 하려면 2개 이상의 값이 존재해야 하기 때문이다.
반복문 종료 시 queue의 맨 앞의 값을 확인하여 K보다 작으면 크기가 1 이하인 조건에서 탈출했으므로 스코빌 지수를 조건에 충족시킬 수 없기 때문에 -1을 반환한다.
위 조건도 통과 시 answer를 반환하게 되면 정답을 받을 수 있을 것이다.
Heap
데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
부모 노드의 인덱스는 1로, 왼쪽 자식노드는 2, 오른쪽 자식노드는 3 순서이다.
- 부모 노드의 인덱스 = 자식 노드 인덱스 // 2
- 왼쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2
- 오른쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2 + 1
배열로 구현할 때 인덱스 번호 1부터 시작하면 편하다.
0부터 할거라면 계산할 때 -1 을 해줘야 한다.
힙은 왜 사용할까?
최솟값이나 최댓값을 찾기 위해 배열을 사용하면 O(n)만큼 시간이 걸린다.
하지만 힙을 사용하면 O(logn)만큼 소요되므로, 배열을 사용할 때보다 빠르게 최솟값과 최댓값을 구할 수 있다.
우선수위 큐와 같이 최댓값 또는 최솟값을 빠르게 찾아야하는 알고리즘 등에 활용된다.
힙의 조건
- 힙은 최대힙(Max heap)과 최소힙(Min heap)으로 나뉘어진다. 최대힙은 자식 노드보다 부모 노드의 값이 크고, 최소힙은 자식 노드보다 부모 노드의 값이 작다.
- 노드가 왼쪽부터 채워지는 완전 이진 트리 형태를 가진다.
- 중복을 허용한다.
완전 이진 트리(Complete Binary Tree)란?
이진 트리에 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리이다.
오른쪽, 왼쪽 구별없이 값이 들어가 있으면 완전 이진 트리라고 할 수 없다.
힙 vs 이진 탐색 트리
이진 탐색 트리(Binary Search Tree)란?
이진 탐색과 연결 리스트(linked list)를 결합한 자료구조의 일종이다.
이진 탐색의 효율적인 탐색 능력을 유지하면서 빈번한 자료의 입력과 삭제를 가능하도록 한다.
각 노드에서 왼쪽의 자식노드는 해당 노드보다 작은 값으로, 오른쪽의 자식 노드는 해당 노드보다 큰 값으로 이루어져 있다.
공통점
- 모두 완전 이진 트리이다
차이점
- (최대힙의 경우) 힙은 각 노드의 값이 자식 노드보다 크거나 같다.
- 이진 탐색 트리는 각 노드의 왼쪽 자식은 더 작은 값으로, 오른쪽 자식은 더 큰 값으로 이루어져 있다.
- 힙은 왼쪽 노드의 값이 크든 오른쪽 노드의 값이 크든 상관없다.
- 힙은 최대/최소 검색을, 이진 탐색 트리는 탐색을 위한 구조이다.
힙의 동작
최대 힙(Max heap)으로 예를 들어 힙의 삽입, 삭제 동작을 알아보자.
데이터 삽입
힙은 완전 이진 트리이기 때문에, 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워진다.
데이터 삽입 (힙의 데이터보다 클 경우)
기본적으로 앞에서 설명한대로, 완전 이진 트리의 구조에 맞춰 최하단부 노드부터 채워진다.
채워진 노드의 위치에서, 부모 노드의 값보다 클 경우에는 부모 노드와 위치를 바꾸며 이를 반복한다.
데이터 삭제
힙 자료구조의 목표는 바로 최대값이나 최소값을 알아내는 것이다.
때문에 데이터가 삭제 된다면 가장 큰 값인 부모 노드의 값이 삭제된다.
그리고 맨 마지막에 있는 값을 가장 위로 올려 밑에 자식 노드중 더 큰 값을 올리는 것을 반복한다.
