[프로그래머스] 더 맵게 - Java [자바]

 

📜 문제 내용

 

🤔 과정

• 문제만 보고 배열과 Arrays.sort 활용해서 풀까 했지만, 문제의 분류가 "힙"으로 되어있어서 힌트를 얻고 PriorityQueue를 사용하게 되었다.
• 우선순위 큐를 사용해 새로운 값을 offer 하면, 내장 메서드를 통해 알아서 이진트리 형식에 따라 오름차순으로 삽입되게 된다. (진짜 오름차순은 아니다. 이진트리 형식이므로.) 

배열을 우선순위 큐에 삽입 -> 가장 맨 앞에 있는(스코빌 지수가 가장 낮은) 음식을 peek하면서 K와 비교하며 반복문 실행 -> 새로운 스코빌 지수 계산한 값을 offer & 섞은 횟수 증가 -> 횟수 or -1 반환

 

✨ 최초 제출 답안

import java.util.*;
import java.io.*;

class Solution {
    public int solution(int[] scoville, int K) {
        
        // Heap 자료구조를 이용한 우선순위 큐 생성
        PriorityQueue<Integer> foods = new PriorityQueue<>();
        for (int i = 0; i < scoville.length; i++) {
            foods.offer(scoville[i]);
        }
        
        int cnt = 0; // 섞는 횟수
        int newScoville = -1; // 섞은 후 스코빌 지수 
        
        // 가장 스코빌 지수가 낮은 음식이 K 보다 크거나 같으면
        // 모든 음식의 스코빌 지수는 K 보다 크거나 같다
        while (foods.peek() < K) {
            newScoville = foods.poll() + (foods.poll() * 2);
            cnt++;
            foods.offer(newScoville);
            
            // 모두 섞어서 남은 음식이 1개라면 멈춘다
            if(foods.size() < 2) break;
        }

        // 가장 스코빌 지수가 낮은 음식이 K 보다 크거나 같으면 cnt 반환
        int answer = (foods.peek() >= K) ? cnt : -1;
        
        return answer;
    }
}

 

• PriorityQueue에 대해 알고 있다면 크게 어렵지 않은 문제였다. 하지만 자주 사용해보지 않아서 이렇게 문제를 풀거나 코테 직전에 이론을 한번 훑을 때 복습할 것 같다. 

 

🔗 문제 링크

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

프로그래머스