99클럽 코테 스터디 5일차 TIL + 힙/ 프로그래머스 [더 맵게]/JAVA

 

 

 

 

1. 오늘의 학습 키워드

---

힙 - (최소힙/최대힙) , 빠르게 탐색할 수 있다, 완전이진트리, 우선순위 큐, 배열

완전이진트리는 마지막 레벨을 제외한 모든 노드가 두 개의 자식을 갖고, 왼쪽부터 자식 노드가 채워져 있는 트리를 말한다. 

JAVA에서는 PriorityQueue 로 우선순위 큐 힙을 선언할 수 있다. 

힙은 우선순위 큐로 내부 구조는 완전이진트리를 하고 있다. 기본적으로 최소힙(루트 노드가 가장 작고, 부모 노드<자식노드, 자식 노드간 순서x)이다. 

선언한 힙에 원소를 add하여 넣으면 자동으로 최소힙으로 만들어준다.  

queue.poll()을 실행하면 힙을 재배치하여 최소힙을 유지한다.  

poll()의 시간복잡도는 O(log n)이고, 전체 n개 원소에 대한 복잡도는 O(n log n)이 된다. 

 

 

 

2. 오늘의 학습 문제 

---

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/42626

프로그래머스

 

 

 

코드

---

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        //우선순위 큐 선언, 루트노드가 가장 작은 최소힙
        PriorityQueue<Integer> pq= new PriorityQueue<>(); 
        
        for(int i: scoville)
            pq.offer(i); //우선순위 큐에 스코빌 삽입 
        
        while(pq.peek() < K){
            if( pq.size() ==1 )
                return -1; //얼리리턴
            pq.offer(pq.poll() + pq.poll()*2); 
            answer++;
            
        }
        
        return answer;
    }
}

 

힙을 통해 풀 수 있는 문제였다. 

힙을 선언하여, 스코빌 지수 원소를 삽입해주어 최소힙을 만든다. 

while문에서 현재 힙의 루트 노드 원소가 K보다 작은지 검사한다.

만약 힙의 사이즈가 1이라면, 모든 음식의 스코빌 지수를 K이상으로 만들 수 없기에 return -1한다.

그렇지 않다면, 주어진 조건에 맞게 가장 낮은 스코빌 지수+ 2번째로 낮은 스코빌 지수*2 로 섞어주어 새로 offer(=add)해주고, answer++한다. 이때 offer()의 복잡도는 마찬가지로 O(log n)이다. 

마지막으로 anwer리턴한다. 

 

3. 오늘의 회고

---

 

힙 자료구조를 이용해 풀어보았는데, 힙의 개념을 더욱 자세히 공부하게 된 것 같다. 그리고 어제 배운 개념인 얼리리턴을 적용해보았다. 파이팅!