[프로그래머스] 힙(Heap) - 더 맵게 문제 풀이

오늘은 드디어 처음 풀게되는 알고리즘 종류인 Heap을 활용한 문제인 "더 맵게" 문제 풀이를 해보겠습니다. 힙을 활용한 문제는 힙 알고리즘의 효율성을 활용한 문제로 풀게될 것 같아 기대가 됩니다.

 

 

프로그래머스 > 힙(Heap) > 더 맵게 문제 풀이

 

 

 

 

 

 

♣ 문제 정보

• 문제명: 더 맵게
• 문제 난이도: Level 2
• 문제 푼 사람수: 25662명
• 사용 가능 언어: 3개(Java 사용)

이 문제가 제가 지금까지 풀어본 사용 가능 언어가 가장 적은 문제인 듯 합니다.

 

 

 

 

♣ 문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

 

 

Leo가 가지고 있는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶어서 스코빌 지수가 낮은 두 음식을 섞어서 음식의 수를 줄이면서 스코빌 지수를 높이면 됩니다. 이 때, 음식을 섞은 횟수를 반환하는 문제입니다. 그럼 문제를 간단하게 정리해보겠습니다.

 

 

• 모든 음식의 최저 스코빌 지수를 K 이상 되도록 하는 음식 섞는 최소 횟수 구하기
• Inputs
  • scoville: 모든 음식의 스코빌 지수 배열
  • K: 모든 음식이 넘어야하는 스코빌 지수
• Output: 모든 음식의 스코빌 지수가 K 이상 되기 위하여 음식을 섞어야하는 최소 횟수

 

 

 

 

♣ 제한 사항

 ⊙ scoville의 길이는 2 이상 1,000,000 이하입니다.
 ⊙ K는 0 이상 1,000,000,000 이하입니다.
 ⊙ scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
 ⊙ 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

 

 

• 2 ≤ scoville의 길이(N) ≤ 1,000,000
• 0 ≤ K ≤ 1,000,000,000
• 0 ≤ scoville의 원소 값 ≤ 1,000,000
• 모든 음식의 스코빌 지수를 K 이상 만들 수 없을 경우 -1을 반환

여기서 N의 길이가 100만이며, K의 크기는 10억입니다. 즉, 효율성 테스트 케이스가 있다는 말이랑 같습니다. 또한 위 제한 사항에서 마지막 문장이 중요합니다. 모든 음식의 스코빌 지수를 K 이상 만들 수 없을 경우도 있다는 생각을 고려하여 알고리즘 및 코드를 구현해야합니다.

 

 

 

 

♣ 입출력 예

scoville	K	return
[1, 2, 3, 9, 10, 12]	7	2

 

 

 

 

♣ 입출력 예 설명

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
    새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
    가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
    새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
    가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

 

 

 

 

♣ 알고리즘 만들기

솔직히 문제 설명 및 제한 사항을 통해서 문제 이해가 어려웠습니다. 이럴 때는 위 입출력 예와 함께, 설명을 자세히 읽어봄으로써 문제의 이해를 도울 수 있습니다. 그럼 더 맵게 문제의 알고리즘을 만들어보겠습니다.

 

이 문제를 풀기 위해서는 적절한 자료구조 활용이 정말 중요합니다. 최소 값을 가장 빠르게 구할 수 있는 최소힙 방식을 활용한 PriorityQueue를 활용하도록 하겠습니다.

 

 

1. 먼저 스코빌 지수 리스트(scoville)을 오름차순으로 정렬한다. (PriorityQueue 활용)
2. 현재 가장 작은 스코빌 지수가 K보다 작은지 확인한다.
   2-1. 작다면 아래를 반복한다.
      2-1-1. 현재 남아있는 PriorityQueue에 있는 음식이 1개인지 확인한다.
         2-1-1-1. 1개라면 -1을 반환한다.
      2-1-2. 스코빌 지수가 K보다 작다면 두 음식을 섞고 PriorityQueue에 넣는다.
      2-1-3. 섞은 횟수를 센다.
3. 2번을 반복해서 얻은 결과를 반환한다.

 

 

 

♣ 코드 구현

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int firstSmall, secondSmall;
        
        // 1. 먼저 스코빌 지수 리스트(scoville)을 오름차순으로 정렬한다. (PriorityQueue 활용)
        for(int i = 0; i < scoville.length; i++) {
            pq.add(scoville[i]);
        }
        
        // 2. 현재 가장 작은 스코빌 지수가 K보다 작은지 확인한다.
        //    2-1. 작다면 아래를 반복한다.
        while(pq.peek() < K) {
            // 2-1-1. 현재 남아있는 PriorityQueue에 있는 음식이 1개인지 확인한다.
            if(pq.size() == 1) {
                // 2-1-1-1. 1개라면 -1을 반환한다.
                answer = -1;
                break;
            }
            // 2-1-2. 스코빌 지수가 K보다 작다면 두 음식을 섞고 PriorityQueue에 넣는다.
            pq.add(pq.poll() + pq.poll() * 2);   
            // 2-1-3. 섞은 횟수를 센다.
            answer++;           
        }
        
        // 3. 2번을 반복해서 얻은 결과를 반환한다.
        return answer;
    }
}

 

 

 

♣ 채점 결과

 

 

역시 이번 문제도 효율성 테스트가 있었습니다. 비중이 컸고, 테스트 시간도 예전 채점 결과에서 본 소요시간들보다 크기가 큽니다. 그럼 이번 더 맵게 문제 풀이에 대한 간단한 정리를 하도록 하겠습니다.

 

 

 

 

♣ 문제 풀이 정리

이번 더 맵게 문제 풀이에 대해서 정리를 해볼까합니다. 제가 지금까지 풀이 했던 문제들은 자료구조보단 논리적인 알고리즘이 더 주요했고 문제 풀이에 있어서 결정적인 역할을 했었습니다. 하지만 이번 더 맵게 문제 풀이에서 알고리즘은 정말 적고 간단했었습니다. 이 문제에서의 키 포인트는 바로 Priority Queue를 알고 있는가? Heap 데이터 구조를 알고 있는가? 에 대한 문제였다고 생각합니다. 그럼 다음에 Priority Queue와 Heap에 대해 공부하는 글을 남겨보겠습니다.

 

 

즉, 역시 알고리즘 문제는 논리적으로 수학적으로 풀어내는 문제와 적절한 자료구조의 활용 모두가 핵심이라고 생각합니다. 이것으로 프로그래머스 더 맵게 문제 풀이를 마치도록 하겠습니다.