힙(Heap)을 활용한 알고리즘 문제풀이

오늘 푼 문제: 더 맵게

• 입력: Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어집니다.
• 출력: 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return합니다.

예제 코드

import java.util.*;

class Solution {
    /**
     * 1. 스코빌 지수가 제일 작은 음식을 조회하여 그 다음 음식과 섞음
     * 2. 스코빌 지수가 제일 작은 음식이 k보다 클때까지 해당 과정을 반복
     * 3. 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우 -1을 return
     */
    public int solution(int[] scovilles, int K) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        // 모든 음식의 스코빌 지수를 PriorityQueue에 할당
        for (int scoville : scovilles) pq.offer(scoville);
        
        while(!pq.isEmpty()) {
            int lowest = pq.poll();
            
            // 스코빌 지수가 가장 작은 음식의 스코빌 지수가 K보다 클 경우 break
            if (lowest >= K) break;
            
            // 모든 음식을 조합해도 스코빌 지수가 K보다 작을 경우 -1을 반환
            if (pq.isEmpty() && lowest < K) return -1;
            
            pq.offer(lowest + pq.poll() * 2);
            answer++;
        }
        return answer;
    }
}

• 힙을 구현한 PriorityQueue를 활용하여 문제를 풀어보았습니다.
• 어제 Early-return 개념과 code-smell 개념을 배웠는데 해당 내용을 적용해보려 노력했습니다.
• Loop에서 모든 조건이 충족된 경우/ 조건을 충족할 수 없는 경우를 먼저 return해줍니다.
• 그 후 스코빌을 조합하는 코드와 cnt를 증가하는 로직을 뒤에 넣어줍니다.

회고

• 오늘도 주석으로 구현 기능을 정해두고 코드를 짰습니다. 뿌듯합니다. * 2
• 조건문을 작성할 때, code-smell을 경계해보겠습니다.
• 오늘은 early return을 구현한 것 같습니다...!