[프로그래머스] 힙(Heap) - 라면공장 (Java)

프로그래머스 코딩테스트 연습 - 힙(Heap) : 라면공장(https://programmers.co.kr/learn/courses/30/lessons/42629) 

프로그래머스

Heap에서 우선순위 큐(Priority Queue)를 사용하는 문제입니다. 우선순위 큐는 java document에 자세히 설명되어 있습니다. 그중에 메서드 부분을 살펴보면

PriorityQueue Method부분

Queue 인터페이스의 메서드

위의 메서드들을 이용했습니다. 우선순위큐는 Queue 인터페이스를 상속받고 있기 때문에 Queue에 대한 doc 내용도 확인하면 좋습니다.

 

저는 위의 문제의 핵심은 supplies 배열에 있는 supply양 정보들을 내림차순으로 정렬해 큰 것부터 하나씩 빼서 조건을 만족하는지 확인하는 것에 있다고 생각했습니다. 최소 외부공급 횟수를 구해야 하는 것이므로 많은 supply를 해주는 date부터 포함을 시켜야 한다고 생각했습니다. 여기에 정렬이 필요한데 Comparable 상속을 통해서 내림차순 정렬을 compareTo Overriding을 통해 설정했습니다.

 

Comparable의 compareTo에서 return값의 의미는 1일 경우 this와 target의 위치를 바꾸겠다는 것입니다. 앞보다 뒤가 더 큰 경우에 바꾸겠다는 것이므로 내림차순이 되겠죠? 일단 저는 이렇게 의미를 이해했습니다.

 

import java.util.*;
 
class Solution  {
    class Flour implements Comparable<Flour>{
        int date;
        int supply;
        
        public Flour(int date, int supply){
            this.date = date;
            this.supply = supply;
        }
        
        @Override
        public int compareTo(Flour target) {
            return this.supply <= target.supply ? 1 : - 1;
        }
 
        @Override
        public String toString() {
            return "date : " + date + ", supply : " + supply;
        }
    }
    
    public int solution(int stock, int[] dates, int[] supplies, int k) {
        int answer = 0;
        
        Queue<Flour> supplyQ = new PriorityQueue<>();
        
        for(int i = 0; i < dates.length; i++){
            supplyQ.offer(new Flour(dates[i], supplies[i]));
        }
        
        Queue<Flour> tmp = new PriorityQueue<>();
        int plusStock = stock;
        while(!supplyQ.isEmpty()){
            
            if(supplyQ.peek().date <= plusStock){
                Flour flour = supplyQ.poll();
                plusStock += flour.supply;
                answer++;
                if(plusStock >= k){
                    return answer;
                }
                
                while(!tmp.isEmpty()){
                    supplyQ.offer(tmp.poll());
                }
                
                
            } else{
                tmp.offer(supplyQ.poll());
            }
        }
        
        return -1;
    }
}

 

출처

- PriorityQueue에서 Comparable을 통한 정렬 : https://cjh5414.github.io/priorityqueue/