힙 (더 맵게)

이번 문제는 heap 문제분류에서 있던 문제이다. 

먼저, heap에 대한 이해가 먼저 되어야 했기에 heap에 대해서 알아보자!

 

heap

- 최댓값, 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리이다.

- A, B가 각각 부모, 자식 노드라면 대소관계가 성립 (최대 힙 -> A>B) / (최소 힙 -> A<B)

- 자식노드의 개수는 일반적으로 2개인, 이진 힙 사용

 

*출처 : ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)

 

java에서 제공하는 heap중에서는 priority queue class를 제공하고 있고

queue와 동작방식은 비슷하지만, 값을 넣었을 때 자동으로 sort가 된다. (최댓값, 최솟값 구하기 너무 좋음,,)

 

priority queue

* queue선언

- Priority queue<[type]> queue = new Priority queue<[type]>();

 

*method 종류

add() : priority queue에 값 넣기

offer() : add와 동일하하게 queue에 값을 넣고, add()와 차이는 offer()은 예외처리 하지 않는다. 

clear() : queue 비우기

comprator() : queue에 있는 값 비교하는 메소드. 정렬방법을 바꾸고 싶으면, overwriting으로 재작성 해야한다.

                  기본적으로 정렬되어 있는게 null 값이다.

contains() : queue에 특정 값을 포함하는지 boolean값을 리턴하는 메소드 (있으면 true, 없으면 false)

peek() : 맨 앞에 값 조회 (queue에서 빼지는 않음)

poll() : queue 맨 앞에 값을 빼냄

remove() : queue에 특정 값 삭제

size() : queue의 사이즈 return

toArray() : queue의 값들을 배열로 반환함.

 

이제 위 문제를 분석해보았을 때,

1. 모든 음식의 값들은 K(스코빌 지수) 이상이 되어야 함.

2. K보다 작은 값 중에서 최소값 2개를 꺼내서 위 공식으로 만들고 다시 queue에 넣고 count하기

3. 모든 값이 K이상일 때, 종료해야하므로 peek()로 검사했을 때 k보다 이상이면 스탑하고 count 리턴

4. 모든 음식을 K이상으로 만들 수 없을 때 -1 리턴 => 배열 길이보다 많은 연산을 했을 때 -1 리턴하기