[PGM_42626] 더 맵게 (Java)

문제링크

https://programmers.co.kr/learn/courses/30/lessons/42626#

코딩테스트 연습 - 더 맵게

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
  Heap

처음에는 그냥 단순하게 초기 정렬 후 삽입정렬로 값을 계속 넣어주었는데 효율성에서 0점을 받았다. 곰곰히 생각해보니 적절한 자료구조로 Heap을 사용하면 되겠다고 생각되어 Heap을 사용해 문제를 해결해 주었다.

 

더 맵게 문제는 매운맛에 대한 배열과 매운 강도 K값이 input으로 주어진다. 모든 매운 맛이 K보다 크거나 같을 때 까지 가장 작은 매운맛과 두번째로 작은 매운 맛을 섞어 더 맵게 만들어주는 문제이다.

 

가장 작은 매운맛을 뽑아주는 것은 Heap을 사용하면 $O(1)$만에 해결할 수 있다. 그리고 그 다음 작은 맛을 뽑아주는 것도 Heap을 사용하면 $O(1)$만에 해결이 가능하다. 매운맛을 다시 넣는 것도 $O(logN)$만에 가능하기 때문에 문제를 쉽게 해결할 수 있다.

 

자바에서는 Heap이라는 Collection이 없지만 PrimaryQueue를 사용하면 Heap을 사용할 수 있게 된다.

2022.01.30 - [CordingTest/Algolithm] - 자바에서 Heap 사용하는 방법  

 

1. 첫번째 매운맛과 두번째 매운맛을 꺼낸다.
2. 두 매운맛을 섞어 새로운 맛을 만든다.
3. 만약 새로운 매운맛이 마지막 매운맛인지 확인하고 처리한다.
   • 만약 새로운 매운맛이 K보다 작다면 -1을 리턴한다.
   • 만약 새로운 매운맛이 K보다 크거나 같으면 answer를 리턴한다.
4. 새로운 매운 맛을 Heap에 넣어준다.

구현코드

package pgm_42626;

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]);
        }

        while(minHeap.peek() < K){
            answer ++;
            int first = minHeap.remove();
            int second = minHeap.remove();
            int newSpicy = first + 2*second;

            if(minHeap.size() == 0)
                if(newSpicy < K)
                    return -1;
                else
                    return answer;

            minHeap.add(newSpicy);
        }

        return answer;
    }
}

 

시간복잡도

Heap에 넣는데 걸리는 시간 $logN$이며, N개의 데이터에 대하여 수행하므로 $O(NlogN)$이다.

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)