문제
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
Yeonju