[Programmers] 더 맵게 - 힙(Heap) JAVA

programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

K보다 작은 수들 중에서 가장 작은수와 그 다음 작은 수를 찾는것이 중요했던 문제.

우선순위 큐를 이용하면 쉽게 풀 수 있었다.

우선순위 큐는 별다른 지정이 없다면, 큐에 들어온 값을 오름차순으로 정렬해준다.

---

풀이

public class Scoville0402 {
    public static int solution(int[] scoville, int K) {
        // 기본 오름차순 정렬
        int count = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>();

        // 1. 음식의 스코빌 지수 큐에 넣기
        for (int spicyLevel : scoville) {
            queue.offer(spicyLevel);
        }

        // 2. K보다 낮은 수 있는지 찾기 (비교할 수는 2개 이상이어야 함)
        while (queue.peek() < K && queue.size() > 1){
            int first = queue.poll();
            int second = queue.poll();

            int mixed = first + (second*2);
            queue.offer(mixed);
            count ++;
        }

        // 제일 낮은 지수가 K값 이상이라면 count 리턴 아니라면 -1
        return queue.peek() >= K ? count : -1;
    }
}

 

• 먼저 PriorityQueue 를 선언한다.
• 스코빌 지수를 PriorityQueue에 모두 담는다.
• 큐에서 꺼낸 값이 (=가장 작은 수) K보다 작고, 큐에는 1개 이상이 담겨 있는 동안 반복
• 첫번 째 꺼내온 값을 first, 두번째 꺼내온 값을 second 로 변수 설정하여 계산한다. 이 때 꺼낸값은 poll(); 메서드를 사용해서 큐에서 바로 제거되고, 계산한 mixed 값을 큐에 넣는다.
• 반복한 횟수 만큼 while 문에서 동작하는 동안 count 변수를 증가시킨다.
• 꺼낸 값이 K보다 크거나 큐 사이즈가 2보다 작아지면 while문이 종료된다.

모든 프로세스가 끝나고, 큐에서 꺼낸값이 K 값 이상이라면 count (횟수)를 리턴하고 아니라면 -1을 리턴한다.

 

---

PriorityQueue (우선순위 큐)

특징

• 우선순위 큐는 일반 큐와 달리 우선순위를 먼저 결정하고, 그 우선순위가 높은 엘리멘터 순서대로 먼저 처리
• 내부 요소는 힙으로 구성되어 있음 (이진트리 구조)
• 내부구조가 힙으로 구성되어 있으므로 시간 복잡도는 O(NlogN)

사용

• java.util 라이브러리를 import
• PriorityQueue<자료형> priorityQueue = new PriorityQueue<>(); 선언
• 기본적으로 오름차순으로 우선순위가 부여됨 (숫자 1, 2, 3, ... 문자 a, b, c, ...)

import java.util.*;

//자료형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<자료형> priorityQueue = new PriorityQueue<>();

//자료형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<자료형> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

메서드

• add(value) : 큐에 값 추가
• offer(value) : 큐에 값 추가
• poll() : 큐에서 첫 번째 값을 반환하고 큐에서 제거 (비어있다면 null)
• peek() : 큐에서 첫 번째 값을 참조
• remove() : 큐에서 첫 번째 값 제거
• clear() : 큐 초기화