프로그래머스 힙 더 맵게 c++ 풀이

보자마자 개껌이네ㅋ 하고 풀었다

int solution(vector<int> scoville, int K)
{
    int answer = 0;

    while (scoville[0] < K)
    {
        answer++;
        scoville[1] = scoville[0] + 2 * scoville[1];
        scoville.erase(scoville.begin());
        sort(scoville.begin(), scoville.end());
    }

    return answer;
}

처참히 실패^^

 

 

int solution(vector<int> scoville, int K)
{
    int answer = 0;

    sort(scoville.begin(), scoville.end());
    if (scoville.back() == 0)
        return -1;

    while (scoville[0] < K)
    {
        if (scoville.size() == 1)
        return -1;
        answer++;
        scoville[1] = scoville[0] + 2 * scoville[1];
        scoville.erase(scoville.begin());
        sort(scoville.begin(), scoville.end());
    }

    return answer;
}

예외상황 몇 개 처리해주고 다시 넣었다.

정확성은 다 맞지만 효율성을... 다 틀려벌임

앞서 스택/큐에서 이중포문으로 풀었을 때 되길래 이번에도 되지 않으려나 했는데 어림도 없군

 

힙을 공부해보기로 했다...

c++ stl 자료구조 중 priority queue를 사용하면 된다

min heap은 부모노드가 항상 자식보다 작은 자료구조이다. c++ stl로는 이렇게 구현된다.

priority_queue< int, vector<int>, greater<int> > pq;

그냥 push만 해도 자동으로 정렬된다고 한다.

 

세상 참 좋아졌군

라떼는 말야 힙을 c로 한땀한땀 구현했다고

 

암튼 이걸 이용해서 다시 풀어보기로 한다. 로직은 이전과 똑같다.

int solution(vector<int> scoville, int K)
{
    int answer = 0;

    priority_queue< int, vector<int>, greater<int> > prices_heap;

    for (int i = 0; i < scoville.size(); i++) 
        prices_heap.push(scoville[i]);

    while (prices_heap.top() < K)
    {
        if (prices_heap.size() == 1)
            return -1;
        answer++;
        int first = prices_heap.top();
        prices_heap.pop();
        int second = prices_heap.top();
        prices_heap.pop();
        prices_heap.push(first + 2 * second);
    }

    return answer;
}

통과~

 

 

개선 아이디어

힙 정렬을 이용했으니 O(n*log n)의 시간 복잡도를 가질 것이다. -> 아님! max(O(), O()answer * log n)) 일 것이다.

시간 효율성을 더 높일 방법은 딱히 생각나지 않는다. 이게 최선인 듯.

코드들을 보니 다들 import heapq를 하셨는데 저는 heap을 몰라서..ㅎㅎ queue만 써서 풀었는데도 시간이 heap을 쓴 풀이의 절반 정도 걸리네요. 저는 섞어서 나온 새로운 값, mix들을 별도의 queue에 넣었는데 이게 가장 큰 요인같네요. 나중에 나온 mix값이 먼저 나온 것보다 클 수밖에 없어서 섞는 순서대로 queue에 넣어주면 크기 순서를 신경 쓸 필요가 없어요. 그냥 popleft로 꺼내면 무조건 mix값의 최소입니다

위와 같은 방법으로 풀면 처음 한번만 정렬을 하면 되니까, 시간 효율성이 훨씬 좋아질 것 같다.

나중에 시간나면 해보기!!

 

다른 사람 코드 분석

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int needHot;
    priority_queue<int,vector<int>,greater<int>> pq (scoville.begin(),scoville.end());

    while(pq.top()<K) {
        if(pq.size()==1) return answer = -1;
        needHot=pq.top(); pq.pop();
        pq.push(needHot+pq.top()*2);
        pq.pop(); answer++;
    }

    return answer;
}

나와 완전 같은 로직이지만 더 심플하다.

1. 포문 돌면서 하나하나 안넣어줘도 그냥 복사연산자로도 되는군
2. 변수 하나만 써도 되는군... 그리고 반복문 안에서 변수를 쓰면 공간복잡도에 안좋다. 앞으로 참고해야겠다~