문제

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

풀이

• 일반 배열로 시도하니 빼고 넣는 과정이 번거로워 풀이를 찾아보니 우선순위 큐로 해결가능한 문제였다

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> que = new PriorityQueue<>();

        for (int i : scoville) {        // 큐에 하나씩 넣어줌
            que.offer(i);
        }

        while (que.peek() < K) {        // 처음 값(제일 작은 값)이 K보다 작지않을 때까지
            if (que.size() == 1) {
                return -1;
            }

            int a = que.poll();         // 첫번째, 두번째 값을 뽑아서 연산
            int b = que.poll();

            int result = a + (b * 2);

            que.offer(result);
            answer += 1;                // 연산할 때마다 +1
        }

        return answer;
    }
}

우선순위 큐(Priority Queue)

• heap, 배열로 모두 구현 가능하지만 heap의 시간복잡도가 더 짧다
  
• heap : 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조이다.
  여러 개의 값 중 최댓값 또는 최솟값을 찾아내는 연산이 빠르다.
  [Algorithm] Tree, Heap
  
  

우선순위 큐

• Queue는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다.
• 우선순위 큐는 들어간 순서에 상관없이 일정한 규칙에 따라 우선순위를 선정하고, 우선순위가 가장 높은 데이터가 가장 먼저 나오게 된다.
  
  

Priority Queue 선언

// int형 우선순위 큐 낮은 순자가 우선순위
PriorityQueue<Integer> que = new PriorityQueue<>(); 
// 낮은 순자가 우선순위

PriorityQueue<Integer> que = new PriorityQueue<>(Collections.reverseOrder); 
// 높은 순자가 우선수위

값 추가, 참조, 삭제

<추가>
add(value)   : 삽입에 성공하면 true 반환,
			   큐에 여유공간이 없어 삽입에 실패하면 IllegalStateException 발생
offer(value)

<참조>
peek() 	 : 우선수위가 가장 높은 값 출력

<삭제>
poll()   : 우선순위 첫번째 값을 반환하고 제거, 비어있다면 null 반환
remove() : 우선순위 첫번째 값 제거
clear()  : queue 초기화

예시

PriorityQueue<Integer> que = new PriorityQueue<>();

que.offer(2);
que.offer(1);
que.offer(3);
que.peek();  // 1, 낮은 순자 순으로 배치되고 우선순위 첫번째 값은 1

p42626 더 맵게 풀이
우선순위 큐
우선순위 큐, 예제 활용법