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

문제보러가기

코딩테스트 연습 - 라면공장

이문제는 힙 알고리즘에 속해 있는 문제이다. 처음 이문제를 봤을 때는 띠용..? 이걸 힙으로 왜 어떻게 접근하지?라고 생각했다 힙에 속해있는지 몰랐다면 탐색 방법으로 풀었을 것 같다. 이문제는 우선순위 큐를 이용하여 풀었다. 접근방식을 떠올리게 되면 구현 자체는 크게 어렵지 않은 문제였으나,힙에 대한 지식, 관련 문제를 많이 접해보지 못한 경우(바로 나 같은..) 헤맬 수 있는 문제였다. 이참에 힙을 시작하여 자료구조를 다시 공부해야겠다고 다짐한 문제이기도 하다!

->힙정리 보러가기

 

 

문제풀이

-최소의 공급을 받는 걸 목표로 하므로 한번 공급될 때 많은 양을 받아야 한다 -> 공급량으로 maxheap을 구성

-stock이 바닥나기 전에 받아야 하므로 stock이 바닥나기 전의 date에 해당하면 일단 haep에 추가한다

-stock이 바닥나는 순간에 가장 많은 양 즉 maxheap의 root값을 가져오고 stock에 추가 후 answer++

-k일 전까지 stock이 0 미만으로 떨어지지 않게 공급해주면서 반복문을 실행한다

 

 

import java.util.Collections;
import java.util.PriorityQueue;

public class Solution{

	public static void main(String[] args) {

		int stock=4;
		int[] dates={4,10,15};
		int[] supplies={20,5,10};
		int k=30; //여기까지 testcase
        
		int answer=0;
		PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
		int index=0;
		//해당하는 날짜일경우 넣을 수 있음 stock이 비거나 그전에 날짜는 사용할수 있으므로
		//4일에 stock이 바닥날경우 1~4일까지 공급받을 수 있는 양에서 가장 큰값을 골라서 받음
		//큰값을 고르는 정렬을 priority큐를 이용함
		for(int i=0;i<k;i++){
			if(index<dates.length && i == dates[index]){
				q.add(supplies[index++]);
			}
			if(stock == 0){
				stock += q.poll();
				answer++;
			}			
				stock--;
		}
		System.out.println(answer);
	}

}