99클럽 코테 스터디 16일차 TIL + 더 맵게

오늘의 학습 키워드 및 문제

#힙 #Heap #PriorityQueue
프로그래머스 2단계) 더 맵게

문제풀이

Heap 자료구조 문제를 풀 때 사용할 수 있는 클래스로 PriorityQueue가 있다는 것을 알고있었다.
큐 문제 공부할 때 알았지 후후
PriorityQueue 클래스는 값을 저장하면 안에서 자동으로 우선순위별 정렬을 해주는데, 값을 꺼낼 때 작은 값 부터 나온다는 특징이 이 문제를 풀기에 적합하다고 생각했다.

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        Queue<Integer> q = new PriorityQueue<>();
        int answer = 0;
        
        // scoville요소를 q에 담기
        for(int i : scoville) {
            q.add(i);
        }

        // q에서 첫번째 요소가 K보다 작을 때 까지
        // 만약, 첫번째 요소가 K보다 작지만 size가 1이면 break
        while(q.peek() < K) {
            if (q.size() == 1) {
                answer = -1;
                break;
            } else {
                int firstMin = q.poll();
                int secondMin = q.poll();
                q.add(firstMin + (secondMin*2));
                answer++;
            }
        }
        return answer;
    }
}

공부한 내용정리

• 자바에는 Heap 자료구조 기반으로 동작하는 PriorityQueue 클래스가 있다.
• PriorityQueue는 우선순위 큐라서 우선순위가 큰 값 (작은 값) 먼저 나온다.
• 내림차순으로 정렬하려면 생성자로 Collections.reverseOrder()를 사용해야 한다.
• 문자열과 문자는 유니코드(ASCII)값 기준으로 정렬한다.
  A, B, C, ..., a, b, c, ..., z