[ TIL - PGS ] 99클럽 코테 스터디 9일차 TIL + 오늘의 학습 가이드

💡 오늘의 학습 키워드

• Heap
• PriorityQueue

 

✅ 오늘 공부한 내용

• PriorityQueue
• Heap
• 오늘의 프로그래머스 문제! 더 맵게

프로그래머스

 

 

👀 오늘의 회고

🤣 오늘의 문제점

• While의 조건문을 똑똑하게 세우자..
• ArrayList를 썼다가 효율성 테스트에서 탈락했다.

 

🔥 어떤 시도를 했는가?

• 초반에는 배열을 추가하고 제거하는 방식을 해야한다는 것에만 꽃혀서 효율성을 따지지 않고 만들었다가 효율성에서 모두 다 탈락하는 그런 사태가 발생하였다..
• 그래서 검색을 해보니 Priority Queue는 우선순위 큐이기 때문에 추가 정렬 등의 소스코드를 짜지 않아도 된다든 것을 발견하게 되었다!
• 해당 구조를 이해하고 풀어보니 아주 쉽고 빠르게 풀 수 있었다.
• 아래는 실패한 소스코드이다.. 지금 다시 보니 매우 비효율적이게 보인다 😂

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        // Leo 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶다.
        // Leo가 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 음식을 만든다.
        
        // 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 스코빌 지수 * 2)
        
        // 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞는다.
        // 모든 음식의 스코빌지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 한다.
        Arrays.sort(scoville);
        
        ArrayList<Integer> arr = new ArrayList<>();
        
        for(int i = 0; i < scoville.length; i++){
            arr.add(scoville[i]);
        }
        
        int start = 0;
        int end = 0;
        int sum = 0;
        int cnt = 0;

        
        while(arr.size() > 1 && Collections.min(arr) < K){
            //if(j >= scoville.length) break;
            Collections.sort(arr);
            
            start = arr.remove(0);        
            end = arr.remove(0);
            
            sum = start + (end * 2);
 
            arr.add(sum);
            cnt++;
            //System.out.println(arr);  
        }
        
        int answer = 0;
        
        if(Collections.min(arr) < K) {
            return -1;
        } else {
            answer = cnt;
        }
        
        return answer;
    }
}

 

• 아래는 성공한 코드이다!

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {

        PriorityQueue <Integer> pQ = new PriorityQueue<>();
        
        for(int i : scoville){
            pQ.add(i);
        }
        
        int cnt = 0;
        
        while(pQ.size() > 1 && pQ.peek() < K){
            int start = pQ.poll();
            int end = pQ.poll();
            
            int sum = start + (end * 2);
            pQ.add(sum);
            
            cnt++;
        }
        
        int answer = 0;
        
        if(pQ.peek() < K){
            return -1;
        } else {
            answer = cnt;
        }
        
        return answer;
    }
}

 

👏 무엇을 새로 알았는가?

• 초반에는 일단 풀어야 했기 때문에 해당 블로그에서 먼저 Priority Queue에 대해 먼저 학습하였다.
• 그 다음으로는 자료구조에서 우선순위 큐와 힙에 대하여 두 개의 블로그를 참고하였다. 긴 내용의 블로그와 짧은 글의 블로그 모두 도움이 되었다.
• Priority Queue란?

// FIFO 구조를 가지면서 순서대로 나가는 것이 아닌 우선순위를 먼저 결정하고 
// 우선순위가 높은 데이터가 먼저 나가는 구조
// 내부 구조는 heap으로 구성되어 이진트리 구조이다.
// 힙으로 구성되어 있기에 시간 복잡도는 O(NlogN)이다.

// Priority Queue 사용법
import java.util.*;

// 낮은 숫자가 우선순위인 우선순위 큐
PriorityQueue<Integer> pQ = new PriorityQueue<>();

// 값 추가
pQ.add(1);

// 첫 번째 값을 반환하고 제거한다. 비어있다면 null 반환
pQ.poll();

// 첫 번째 값을 반환한다. 비어있다면 null 반환
pQ.peek();

// 큐가 비어있는지 boolean 형식으로 알려준다.
System.out.println(pQ.isEmpty());

 

 

👩‍💻 내일은 무엇을 학습할 것인가?

• 항해 99 문제 풀기
• 코테 스터디 진행하기
• 자소서 쓰기