[99클럽 4기 코테 스터디 TIL 25일차] 더 맵게 (feat. 최소힙)

1) 문제

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

프로그래머스

 

 

 

2) 내가 작성한 코드 및 오류부분(수정한코드 포함)

• 비교적 쉬웠음에도 불구하고 몇가지 놓친 부분이 있었다.
  • 1. 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우의 로직을 어떻게 판단하며 어디에 넣을 것인가?
  • 2. 스코빌을 섞을 때 힙 안에 값이 2개 이상인지 체크를 어떻게 할것인가?

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        // 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1 return (X)
        // -1을 리턴하는 경우는 맨 마지막에 힙의 들어있는 요소에서 K값과 비교한다!!!!! - 바보..ㅠ
        //int tot = 0;
        //for(int scov : scoville) tot += scov;
        //if(tot < K) return -1;

        PriorityQueue<Integer> pq = new PriorityQueue<>(); // 최소힙
        for(int scov : scoville) pq.add(scov); 
        
        
        //!pq.isEmpty() 로 비어있는지 체크를 하는 것이 아니고, 적어도 2개 이상 남아야 아래의
        //로직이 수행되므로 pq.size() > 1 로 체크하는 것이 맞음
        //pq.poll()의 경우 값이 없으면 null을 반환하지만, 연산결과에서 오류가 날 것이다!!!
        while(pq.size() > 1 && pq.peek() < K) { // 큐에 두 개 이상의 요소가 있는지 확인
            int first = pq.poll();
            int second = pq.poll();
            pq.add(first + (second * 2));
            answer++;
        }
        
        
        // 마지막으로 확인: K 이상의 스코빌 지수가 있는지 (O)
        if(pq.peek() < K) return -1;

        return answer;
    }
}

 

 

3) 추가문제

미들러 - 주사위 쌓기

https://www.acmicpc.net/problem/2116

 

챌린저 - 로봇 조종하기

https://www.acmicpc.net/problem/2169