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

문제

---

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

 

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

 

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

제한 사항

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

입출력 예

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회입니다.

---

풀이

 

이 문제는 수가 많은 것과 적을 때가 크게 중요하지 않은 문제이다. 우선 입출력 예시를 살펴보면 해당 배열은 정렬되어 있다. (만약 정렬되지 않은 경우, 고려해야 할 경우를 줄이기 위해 오름차순으로 정렬을 하도록 한다!)

 

< 입출력 예시를 통해 문제 살펴보기 >

 

1회차 : 1 2 3 9 10 12    K=7

섞기 ) 1+(2*2) = 5  ---> 정렬이 이미 되어있는 배열이므로, 3 뒤에 원소를 삽입한다.

 

2회차 : 3 5 9 10 12   K=7

섞기 ) 3+(5*2) = 13  ----> 12 뒤에 원소를 삽입한다.

 

3회차 : 9 10 12 13   K=7

스코빌 지수 K보다 가장 작은 원소 9가 더 크므로 몇번 섞었는지에 대한 count를 return한다.

 

< 알고리즘의 복잡도 >

 

- 최악의 경우 : 모든 음식을 전부 살펴보는 경우.

음식이 n개인 경우, n-1회를 살펴보아야 한다.

 

- 각 단계(섞기)에서 요구되는 계산량 

  : 정렬된 리스트 순서에 맞춰 원소 삽입 -> 정렬된 리스트의 길이에 비례함

    --> O(n)

 

- 전체 문제 풀이의 복잡도

 : n번의 단계를 거쳐, 각 단계에서 n에 비례하는 계산을 하므로, 최종적으로 O(n^2) ---> 지나치게 높다!

   --> 뭔가 더 좋은 방법? : 힙!

 

< 보다 나은 방법 >

최소/최대 원소를 빠르게 꺼낼 수 있으면 BEST! -> 힙(Heap) 사용

 

힙의 종류

- max heap : 최대 원소를 빠르게 꺼낼 수 있음

- min heap : 최소 원소를 빠르게 꺼낼 수 있음

 

힙의 특징 : 최소/최대 원소를 빠르게 찾을 수 있음 (상수 시간 소요)

 

힙의 연산 : 힙 구성(heapify), 삽입(insert), 삭제(remove) 

* 힙 구성 : 배열로 힙 생성 : O(NlogN) -> 하나의 원소를 삽입하는데 logN만큼 걸리고, n개의 원소를 삽입해야 하므로!

* 삽입 : 임의의 원소를 힙의 순서가 흐트러지지 않도록 삽입 : O(logN)

* 삭제 : 최소/최대 원소를 삭제하며, 이 역시 힙의 순서가 흐트러지지 않도록 삽입 : O(logN)

( 꺼내는 것 자체는 상수 시간이나, 꺼낸 후 힙의 순서를 유지하도록 하는데에 O(logN) 시간 소요)

 

힙의 구현 : 완전 이진 트리 -> 배열을 이용해서 구현 가능 (공간효율성 높음)

 

max heap

<- Max Heap

root node : 가장 큰 원소(30)

 

 

 

 

 

 

 

 

 

 

 

 

 

힙의 응용

- 정렬(heapsort) : 최악의 복잡도 = 최적의 복잡도

- 우선 순위 큐 

 

---

C++ 코드 (힙으로 구현)

 

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0; // 몇번이나 음식을 섞었는가
    
    priority_queue <int, vector<int>, greater<int>> q;
    for (auto& i : scoville){
        q.push(i);
    }
    while(true) {
        int min1 = q.top();
        q.pop();
        // 제일 덜매운 음식의 스코빌 지수가 K보다 클때
        if (min1 >= K) break;
        // 다 봤는데도 K가 제일 클때 (실패)
        else if (q.empty()) {
            answer = -1;
            break;
        }
        // 스코빌지수 계산
        int min2 = q.top();
        q.pop();
        q.push(min1 + 2 * min2);
        answer++;
    }
    
    return answer;
}

 

코드 분석

for(auto& i : scoville) {
	q.push(i);
}

시간 복잡도 : O(NlogN)

 

while(true) {
        int min1 = q.top(); q.pop(); // O(logN)
        if (min1 >= K) break;
        else if (q.empty()) {
            answer = -1;
            break;
        }
        int min2 = q.top(); q.pop(); // O(logN)
        q.push(min1 + 2 * min2); // O(logN)
        answer++;
}

 전체 while문 시간 복잡도 : 최악의 경우 O(n-1), n에 비례하는 반복횟수를 가짐

-> 전체적인 알고리즘의 복잡도 : O(NlogN)

 

---> 최종적으로, 알고리즘의 시간 복잡도 : O(NlogN)