[Java] Progrmmers 코딩테스트 연습 : 라면공장 (Heap)

---문제---

 

문제 설명

라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다.

해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다.

현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 return 하도록 solution 함수를 완성하세요.

dates[i]에는 i번째 공급 가능일이 들어있으며, supplies[i]에는 dates[i] 날짜에 공급 가능한 밀가루 수량이 들어 있습니다.

 

제한사항

• stock에 있는 밀가루는 오늘(0일 이후)부터 사용됩니다.
• stock과 k는 2 이상 100,000 이하입니다.
• dates의 각 원소는 1 이상 k 이하입니다.
• supplies의 각 원소는 1 이상 1,000 이하입니다.
• dates와 supplies의 길이는 1 이상 20,000 이하입니다.
• k일 째에는 밀가루가 충분히 공급되기 때문에 k-1일에 사용할 수량까지만 확보하면 됩니다.
• dates에 들어있는 날짜는 오름차순 정렬되어 있습니다.
• dates에 들어있는 날짜에 공급되는 밀가루는 작업 시작 전 새벽에 공급되는 것을 기준으로 합니다. 예를 들어 9일째에 밀가루가 바닥나더라도, 10일째에 공급받으면 10일째에는 공장을 운영할 수 있습니다.
• 밀가루가 바닥나는 경우는 주어지지 않습니다.

 

---코드---

 

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

public class Heap_2 {
	public static void main(String[] args) {
		int stock=5;
		int[] dates= {5,6,7,10,11,15,16,20,22,30,36};
			//{3,4,6,10,15,16,17};
		int[] supplies= {10,10,20,10,10,10,1,1,1,1,10} ; // 정답은 3
			//{10,6,10,10,30,20,5}; // 정답은 3
		int k = 40;
		int cnt = 0 ;
		PriorityQueue<Integer> pq = 
        			new PriorityQueue<Integer>(Collections.reverseOrder());
		if(stock >= k) {
			System.out.println(0);
		}
		else {
			int i= -1;
			while(stock<k) {
				while(i<dates.length-1&&dates[++i]<=stock) {
					pq.offer(supplies[i]);
				}
				--i;
				
				stock += pq.remove();
				++cnt;
			}
		}
		System.out.println(cnt);
	}
}

 

이 문제는, dates 에 따라서 필수적으로 선택해야 하는 구간이 있기 때문에 이를 고려해야한다.

이에 대한 예로 , 처음에 stock 이 4인 경우 4일이 되기 전에 한번은 밀가루를 꼭 공급받아야 한다.

대신, 이렇게 밀가루를 꼭 공급받아야 할 때, 그 날짜 전에 가능한 공급 후보 중에서 공급량이 최대값인 곳을 선택해야 한다.

이런 이유로 java 에서 PriorityQueue 자료 구조를 사용하게 되었다.

PriorityQueue 에 무조건 공급받아야 하는 날짜 전에 모든 후보들을 저장하고

이 중에서 최댓값을 꺼내서 stock에 추가하고 자료구조에서 지우는 방식이다.

 

이 문제를 푸는데 핵심은 

자료구조에서 root 가 가장 최솟값을 가지는 min Heap 이 기본으로 되어있는 PriorityQueue를 

최댓값을 root 로 할 수 있도록 바꾸어 주는 과정이다.

 

필자는 이 과정을

PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());

이렇게 표현했는데, 이것은 아래에 작성한 PriorityQueue의 constructor를 참고하면 이해가 쉽다.

Java Platform SE7

PriorityQueue(Collection<? extends E> c)

Creates a PriorityQueue containing the elements in the specified collection.

 

PriorityQueue(int initialCapacity, Comparator<? super E> comparator)

Creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator.

첫번째 인자에, 처음에 지정할 용량(Capacity)를 지정해주고, Comparator 클래스를 overriding 해주는 것이다.

근데 직접 overriding하지 않고, Collections class에 작성된 reversOrder를 끌고와서 작성하였다.

 

직접 overriding 을 한다면 다음과 같이 생성자를 불러오면 된다.

//main 전에 import 해주고
import java.util.Comparator;
import java.util.PriorityQueue;

public class Heap_2 {
	public static void main(String[] args) {
    
      	 PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {

                  @Override
                  public int compare(Integer a1, Integer a2) {
                      return a2 - a1;
                  }
                  
              });
              
              // 생략
    }
}

 

 

---출처---

https://programmers.co.kr/learn/courses/30/lessons/42629

코딩테스트 연습 - 라면공장 | 프로그래머스