🔗 문제 링크
https://programmers.co.kr/learn/courses/30/lessons/42626
🤔 문제
매운 것을 좋아하는 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 합니다.
😮 문제 해결 방법
최소 힙(우선순위 큐)을 이용해서 문제를 접근하고 해결을 위한 세 가지 조건을 먼저 구성했다.
- 큐의 가장 앞 요소(최소 값)이 K와 같거나 K보다 큰 경우
- 큐의 Size가 1인 경우 즉, scoville 배열의 원소가 1개인 경우
- 큐의 가장 앞 요소(최소 값)이 K보다 작고 큐의 Size가 1보다 큰 경우
PriorityQueue<Integer> pq = new PriorityQueue<>();
//우선 순위 큐에 데이터 넣기
for(int scv : scoville)
pq.offer(scv);우선 순위 큐에 들어간 원소들은 항상 완전 이진 트리를 구성하며, (최소 힙의 경우) 최소 값이 트리의 루트에 들어가고 큐에 원소가 삽입될 때 항상 트리의 단말 노드로 들어가 부모 노드와 비교해 삽입된 원소가 더 작으면 swap해주며 구성된다.
👉🏻첫번째 조건 확인 👈🏻
10,7,8,5,9로 구성된 scoville배열이 주어지고, K값이 5인 경우를 예로 들어보자.
큐에 원소를 삽입하면 {5,8,7,10,9}순으로 노드가 삽입된다. 우선순위 큐에서 가장 앞 원소가 5이고 최소값이면서 K와 같기 때문에 음식을 섞어줄 필요가 없다. 따라서 count(0)을 return하면 된다.
//큐 size가 1인 경우 값 비교만 필요
//큐의 가장 최소 값이 K 이상인 경우 음식 섞어줄 필요 x
while(pq.size()>1 && pq.peek() < K)👉🏻두번째 조건 확인 👈🏻
큐의 size가 1인경우에는 while문의 조건을 들어가지 않기 때문에 음식을 섞어줄 필요가 없다. 따라서 값이 K보다 큰지 작은지만 비교해서 -1 혹은 count(0)를 return 해주면 된다.
if(pq.peek() < K )
return -1;👉🏻세번째 조건 확인 👈🏻
3,2,4,6,1로 구성된 scoville배열이 주어지고, K값이 14인 경우를 예로 들어보자.
큐에 원소를 삽입하면 {1,2,4,6,3}순으로 노드가 삽입된다. 우선순위 큐에서 가장 작은 원소 1과 그다음 작은 원소 2를 문제의 공식대로 음식을 섞어주면 1 + (2*2) = 5가 되고 다시 우선순위 큐에 넣어준다. 그렇다면 {2,3,4,6,5}가 된다. 이러한 방식을 가장 앞 원소가 K보다 크거나 같은 수가 될 때까지 반복하고 반복횟수를 세어서 return해주면 된다.
아래는 Java로 구현한 코드이다.
🚩 JAVA 코드
package com.algorithm.Programmers.Lv2;
import java.util.PriorityQueue;
public class Solution_42626 {
public static void main(String[] args) {
int[] scoville = {3,2,4,6,1};
int k = 14;
System.out.println(solution(scoville,k));
}
public static int solution(int[] scoville, int K) {
int answer = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>();
//우선 순위 큐에 데이터 넣기
for(int scv : scoville)
pq.offer(scv);
for(int s : pq)
System.out.println(s);
//큐 size가 1인 경우 값 비교만 필요
//큐의 가장 최소 값이 K 이상인 경우 음식 섞어줄 필요 x
while(pq.size()>1 && pq.peek() < K){
int first = pq.poll();
int afterScov = 0;
//최소 값이 K 보다 작으면 음식 섞기
if(pq.peek() < K){
afterScov = first + (pq.poll() * 2);
pq.offer(afterScov);
answer++;
continue;
}
//최소 값이 K보다 큰 경우 마지막으로 음식 섞어주기
afterScov = first + (pq.peek() * 2);
pq.offer(afterScov);
answer++;
}
//최소 값이 기대 스코빌 지수보다 작으면 만들 수 없는 경우
if(pq.peek() < K )
return -1;
return answer;
}
}📄 정리
- 알고리즘을 풀면서 처음으로 힙(우선순위 큐)를 사용해봤다. 높은 우선순위의 요소를 먼저 처리하고 이진트리 구조로 이루어져 있기 때문에 시간 복잡도도 O(NLogN)이다.
- 요소의 최소 혹은 최대를 묻는 문제에 적용하면 효율성이 좋을 것 같다.
- 오랜만에 힙을 사용하게 되면서 힙의 삽입, 삭제 연산의 구조에 대해서도 다시 리마인드하는 계기가 되었다.
