99클럽 코테 스터디 5일자 TIL + 힙(heap)

문제 출처

https://school.programmers.co.kr/learn/courses/30/lessons/42626 (프로그래머스)

학습 키워드

힙(HEAP)

시도 방법

우선순위큐를 활용해 문제 풀이 (성공)

내가 작성한 코드

import java.util.Queue ; 
import java.util.PriorityQueue; 

class Solution {
    public int solution(int[] scoville, int K) {
        
        //우선순위큐 : 우선순위가 높은 순서로 정렬되는 큐 (1이 높은거임)
        //내부로 힙 자료구조를 이용한다.        
        Queue<Integer> priorityQueue = new PriorityQueue<>(); 
        int shake = 0;
        
        for (int num : scoville) {
            priorityQueue.add(num); //추가될때마다 수치에 맞춰 정렬됨
        }
        
        while(priorityQueue.size() >= 2) {
            
            if(priorityQueue.peek() >= K) {
                return shake; 
            }

            shake += 1 ; 
            priorityQueue.add(priorityQueue.poll() + priorityQueue.poll() * 2); 
        }
        
        return priorityQueue.poll() >= K ? shake : -1; 
    }
}

코드설명

우선순위큐는 데이터를 넣으면서 동시에 내부적으로 정렬처리가 된다.
우선순위가 1인 경우가 100인 경우보다 높은 예시이므로
만약 3 , 1 , 2 순서대로 데이터를 우선순위큐에 입력한다면 [1,2,3] 이 되는 것이다.

해당 문제는 스코빌 지수가 가장 낮은 음식 ( = 우선순위큐에서 앞의 데이터 2개) 을 섞어서
다시 큐에 등록하고 있다.

예를 들어 [1,2,3,9,10,12] 가 있다면 앞의 1,2가 로직이 따라 5 (1 + 2*2) 가 된다.
이 5를 다시 큐에 등록하면 [3, 5 ,9,10,12] 가 되는 것이다.(자동 정렬 처리)

stack이 비어있지 않고, 마지막으로 들어있는 값이 ( 이면서[peek] , 현재 값이 ) 이라면 stack에서 pop을 통해 마지막의 데이터를 빼낸다.

이 작업을 큐의 데이터가 1개만 남을때까지 반복을 하고 해당 결과가 K값보다 크거나 값다면 K를 아니면 -1를 반환한다.

새롭게 알게된 점

힙의 자료구조에 대해 공부를 함으로써 힙을 더 이해할 수 있었다.

다음에 풀어볼 문제 - smallest-number-in-infinite-set(리트코드)

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL