-
[프로그래머스] 더 맵게Algorithm 2020. 9. 9. 14:17반응형
매운 것을 좋아하는 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 합니다.
import java.util.*; class Solution { public int solution(int[] scoville, int K) { int answer = 0; PriorityQueue<Integer> pq = new PriorityQueue<>(); int index = 0; for(int i : scoville){ pq.add(i); if(K <= i) index++; } if(index == scoville.length) return 0; while (pq.peek() < K){ try { index = pq.poll() + (pq.poll()*2); pq.add(index); answer++; } catch (NullPointerException e){ return -1; } } return answer; } }
반응형'Algorithm' 카테고리의 다른 글
[프로그래머스] 비밀지도 (0) 2020.09.09 [프로그래머스] 다트게임 (0) 2020.09.09 선택정렬 - 오름차순,내림차순 (0) 2020.02.14 [백준 N10815] 이분탐색.숫자카드 (0) 2019.10.03 [백준 N2805] 이분탐색.나무자르기 (0) 2019.10.03