[프로그래머스-코딩테스트 연습] 힙 - 더 맵게 (20.02.03)

 

시작한 지 5일 만에 다시 시작하는 코테 연습 ㅎㅎ,,,

 

월요일 문제 담당인 내가 지정한 문제

오랜만에 힙을 골라봤다

사실 가장 쉬워 보이는 걸로 골라봤다 ㅎ

 

 

 

프로그래머스 코딩 테스트 연습

힙(Heap)- 더 맵게 (2단계)

 

 

 

문제 사이트 : https://programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게 | 프로그래머스

- 스코빌 지수가 가장 낮은 두 개의 음식을 특별한 방법으로 섞어 새로운 음식을 만든다.

 즉, 2개 이하의 노드만을 가지는 MinHeap 클래스를 만들어 문제를 풀면 아주 쉬워진다.

 

- 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return (이 부분은 잊지 말 것!)

 

 

 

 

 

 

 

---

 

 

 

직접 작성해본 소스코드 및 간단한 설명

 

#include <string>
#include <vector>
using namespace std;
#define  MAX_ELEMENT    1000000
 
class HeapNode
{
    int            key;
public:
    HeapNode(int key = 0) : key(key) { }
    ~HeapNode(void) { }
 
    void     setKey(int k) { key = k; }
    int     getKey() { return key; }
    void     display() { printf("\t%d", key); }
};
 
class MinHeap
{
    HeapNode     node[MAX_ELEMENT];
    int         size;
public:
    MinHeap() : size(0) { }
    bool isEmpty() { return size == 0; }
    bool isFull() { return size == MAX_ELEMENT - 1; }
 
    HeapNode&    getParent(int i) { return node[i / 2]; }
    HeapNode&    getLeft(int i) { return node[i * 2]; }
    HeapNode&    getRight(int i) { return node[i * 2 + 1]; }
 
    void insert(int key) {
        if (isFull()) return;
 
        int i = ++size;
 
        while (i != 1 && key < getParent(i).getKey()) {
            node[i] = getParent(i);
            i /= 2;
        }
        node[i].setKey(key);
    }
    
    HeapNode remove() {
        if (isEmpty()) return NULL;
 
        HeapNode root = node[1];
        HeapNode last = node[size--];
 
        int parent = 1;
        int child = 2;
 
        while (child <= size) {
            if (child < size && getLeft(parent).getKey() > getRight(parent).getKey())
                child++;
            if (last.getKey() <= node[child].getKey()) break;
 
            node[parent] = node[child];
            parent = child;
            child *= 2;
        }
        node[parent] = last;
        return root;
    }
    
    HeapNode find() { return node[1]; }
};
 
int solution(vector<int> scoville, int K) {
    MinHeap heap;
    for(int i = 0; i< scoville.size(); i++)
        heap.insert(scoville.at(i));
    int count = 0;
    while(heap.find().getKey() < K){
        int first = heap.remove().getKey();
        int second  = heap.remove().getKey();
        heap.insert(first + second*2);  
        count++;
        if(count >= scoville.size()-1){
            count = -1;
            break;
        }
    }
    return count;
}

 

 

사실 조금 귀찮아서 기존에 만들어 놨던 코드들을 이용했다.

간단하게 중요한 부분을 설명하자면,

 

 

 

●  HeapNode class

   데이터가 int 여도 되므로 데이터 타입은 int를 사용

 

 

 

●   MinHeap class

    remove() 함수와 insert(int key) 함수의 내용이 가장 중요하다.

 

 

 

 

●   solution 함수  

   MinHeap 객체 생성 후, 모든 scoville안의 요소들을 insert 해준다.

   MinHeap은 가장 작은 수가 첫 번째 요소이므로 find() 함수를 통해 K와 비교해준다.

 

   그 후 remove() 함수를 통해 가장 작은 수와 그다음으로 작은 수를 받아와서 계산 후 insert 해준다

   이때 계속적으로 count를 세주면 이는 우리가 원하는 return 값이 된다.

 

  '모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return '

 

   이 조건을 만족해주기 위해서 모든 음식의 스코빌 지수를 확인한 상태인 count가 scoville 요소의 개수보다 같거나 크   게 되는 경우, count를 -1로 만들어주고 break;를 통해 반복문을 나와주면 된다.

 

 

 Heap의 성질을 이용하여 MinHeap 클래스를 짜낼 수만 있다면 아주 간단했던 문제이다. ⌒▽⌒

 

 

 

 

 

 

 

 

---

 

 

 

 

프로그래머스로 채점 결과

 

1018점

2단계여서 그런지 보너스 점수가 조금 더 늘었다!!

 

 

 

 

 

 

 

 

 

 

 

 

---

 

 

 

 

제출 후 다른 풀이와 비교해 본 소감

 

- 힙 문제지만, 그 원리를 이용해서 "queue.h"를 사용해서 문제를 푸는 방법도 있다.

  후에 다시 풀어볼 것! (대부분이 이 헤더 파일을 사용했기 때문.)