[프로그래머스]라면공장 문제풀이(우선순위큐)

우선순위 큐를 이용하기. 

우선순위 큐는 항상 정렬된 자료 구조! (넣는 순간 sort가 된다)

=> Poll() 하면 항상 첫번째 정렬된 값이 나온다?

 

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Comparator.reverseOrder()); // 내림차순(Poll하면 큰거부터나옴)
PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>();  // 오름차순 (Poll하면 작은거부터 나옴)

 

package OneDayOneCodingChallenge;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import org.junit.Assert;
import org.junit.Test;

/**
 * @author seoyeon on 2020/09/07
 * @project AlgorithmTest
 */

public class Day4 {

  public int solution(int stock, int[] dates, int[] supplies, int k) {

    int answer = 0;
    Queue<Integer> priorityQueue = new PriorityQueue<>(Comparator.reverseOrder());

    int index = 0;

    for (int i = 0; i < k; i++) {
      if (index < dates.length && i == dates[index]) {
        priorityQueue.add(supplies[index++]);
      }
      if (stock == 0) {
        stock += priorityQueue.poll();
        answer++;
      }
      stock -= 1;
    }
    return answer;
  }

  @Test
  public void 정답() {
    Assert.assertEquals(2, solution(4, new int[]{4, 10, 15}, new int[]{20, 5, 10}, 30));
  }

}