[Java] 프로그래머스(level-2) - 더 맵게

문제 풀이

---

이번 문제는 우선순위 큐를 활용한 최소 힙을 구현하여 풀 수 있다.

아이디어 도출

이 문제는 힙에 대한 지식이 어느정도 필요하다.

여기서 말하는 Heap(힙)은 최소값 및 최대값을 최대한 빠르게 찾아내기 위해 특별히 고안된 자료 구조이다.

Java에서는 일반적으로 우선순위 큐인 PriorityQueue를 이용해 힙을 구현한다.

PriorityQueue는 우선순위 큐를 구현한 자료구조로서, 내부적으로 이진 힙(Binary Heap)을 사용하여 요소들을 저장하고 관리한다. 이진 힙은 완전 이진 트리의 형태를 갖춘 특별한 형태의 힙 자료구조로서, 최소 힙 또는 최대 힙의 형태로 사용될 수 있다.

여기서 중요한 점은 바로 우선순위 큐를 이용하면 큐의 원소들은 우선순위에 따라 자동으로 정렬된다, 즉 우선순위를 설정하여 정렬할 수 있다는 것이다. 문제대로라면 스코빌 지수가 K 이상이 되도록 모든 음식을 섞어야 하기에 첫번째 최소값과 두번째 최소값을 알기 위해 큐를 오름차순으로 정렬해 두어야 한다.

이러한 우선순위 큐를 이용해 문제 풀이를 위한 아이디어는 다음과 같다.

1. 우선순위 큐의 우선순위를 최소로 설정한다.(PriorityQueue는 기본값으로 최소값이 우선순위가 되도록 제공한다.)
2. 우선순위큐에 scoville의 원소들을 담는다.
3. 큐의 첫번째 값이 K보다 작다면, 첫번째 최소값 + (두번째 최소값 * 2) 연산을 수행해 큐에 재삽입한다.
4. 3번 과정을 반복하며 섞는 횟수를 1 증가시킨다.
5. 위 3-4번 과정을 반복하며 큐의 첫번째 값이 K보다 크다면 순회를 종료하고 섞는 횟수를 출력한다.
6. 이때, 첫번째 값이 K보다 작다면 모든 수를 K 이상으로 만들 수 없기에 종료하고 -1을 출력한다.

다음으로 문제 풀이를 위해 작성한 코드는 아래와 같다.

작성 코드

---

import java.util.*;

class Solution {

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

        // 1. scoville의 최솟값이 K보다 커야 한다.
        // 2. 최솟값이 K보다 작다면, 섞어야 한다.
        // 3. 첫번째 최소값+(두번째 최솟값*2) 연산의 값을 다시 삽입한다.
        // 4. 위 1-3번 과정을 반복하며 scoville의 최소값이 K보다 크다면 섞은 횟수를 출력한다.
        // 5. 이때, scoville을 우선순위 큐를 이용해 최소 힙처럼 사용한다.

        // 우선순위 큐 선언
        // 기본으로 최소값을 우선으로 두는 힙처럼 사용할 수 있다.
        PriorityQueue<Integer> q = new PriorityQueue<>();

        for(int i=0; i<scoville.length; i++) {
            q.offer(scoville[i]);
        }

        // 스코빌 지수를 K 이상으로 만들기 위해 섞는 횟수
        int answer = 0;
        
        // 모든 음식을 K 이상으로 만들 수 있는지 여부를 담을 변수
        boolean possiable = true;

        while(q.peek() < K) {
            // 큐의 원소가 하나남았음에도 K를 만들지 못한다면 
            // 모든 원소를 K 이상으로 만들지 못하기에 순회를 종료한다.
            if(q.size() == 1 && q.peek() < K) {
                possiable = false;
                break;
            }
            
            // 첫번째 최소값+(두번째 최솟값*2) 연산한 값을 큐에 재삽입한다.
            int first_min = q.poll();
            int second_min = q.poll();
            q.offer(first_min+(second_min*2));
            
            // 섞는 횟수를 1 증가시킨다.
            answer++;

        }
        
        // 모든 원소를 K 이상으로 만들지 못하기에 -1을 반환한다.
        if(!possiable) {
            return -1;
        }

        return answer;
        
    }


    public static void main(String[] args) {
        
        Solution sol = new Solution();
        
        // int[] scoville = new int[]{1, 2, 3, 9, 10, 12};
        // int K = 7;
        int[] scoville = new int[]{1, 1, 2, 6};
        int K = 24;

        sol.solution(scoville, K);

    }

}

회고

- —

출처

- —

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.