[Programmers] Lv2_더 맵게 (JAVA)

💻JAVA 코드 바로보기



□문제 설명

매운 것을 좋아하는 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 합니다.

---

□입출력 예

scoville	K	return
[1, 2, 3, 9, 10, 12]	7	2

---

🌼 JAVA 알고리즘

 

 

□초기화면

 

 

 

 

 

 

 

□풀이과정

문제를 풀기 전에, 문제유형인 '힙(Heap)'에 대해 알아보자. java에선 heap에서도 최소힙 구성을 해주는 Priority Queue 을 지원한다. 최소힙은 아래와 같이 값을 크기 순서대로 넣지 않아도 자동으로 내림차순을 구성해준다. 더 자세한 내용은 아래의 블로그에서 잘 설명해주고 있으니 참고하면 좋을 것 같다. -> 저장 순서 : 0,2,4

	minHeap.add(2);
        minHeap.add(0);
        minHeap.add(4);

 

Java Heap & Priority Queue

JAVA로 알아보는 힙 (Heap) 자료구조

최소힙을 사용함으로써 Arrays.sort와 같은 정렬 알고리즘을 직접 사용할 필요가 없고, 코드의 효율성 또한 좋아진다. 문제를 해결하기 위해서, PriorityQueue를 초기화한 이후 두개의 값을 poll(stack의 pop과 동일한 기능)해주어 섞은 음식의 스코빌을 계산한다. 최소값(peek한 결과값)이 K보다 커질때까지 계속해서 스코빌이 작은 두개의 음식을 섞고 추가(add)해주는 방법을 사용했다.

 

 

 

 

 

 

 

 

 

□완성 코드

import java.util.PriorityQueue;
class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        //최소힙 생성, 초기화
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for(int i=0;i<scoville.length;i++){
            minHeap.add(scoville[i]);
        }
        //K
        while(minHeap.peek()<K){
            answer++;
            //만들 수 없을 경우
            if(minHeap.size()<2) return -1;
            //음식 섞어 최소힙에 추가
            int mixed = minHeap.poll() + minHeap.poll()*2;
            minHeap.add(mixed);
        }
        
        return answer;
    }   
}

 

 

 

 

 

 

---

□링크

About Me

코딩테스트 연습 - 더 맵게