프로그래머스 - 힙/ 더 맵게 문제 c++

처음에는 vector를 그냥 sort사용해서 정렬한다음

첫번째 원소를 erase해주고

두번째 원소를 erase해준 다음,

새로운 new_sco를 계산해서 insert로 넣어줬다.( iterator를 사용하여 넣어줬다)

그랬더니 효율성 체크에서 실패가 떠서

코드를 아예 다른 방식으로 접근해야했다..

누가봐도 큐스러운 문제가 있을때는 그냥 큐를 사용하자...! 괜히 벡터로 sort하고 뭐해도 실행시간 때문에

실패하는 경우가 많다...

사실 큐는 알고있었는데 기말고사로 코테를 잠시 손을 놔서 그런지 pritority_queue가 생각나지 않았다..

원래부터 모르고있던건지 까먹은건지 모르겠지만

무튼!

priority_queue를 사용해서 풀면된다

priority_queue를 greater를 사용하여 오름차순으로 정렬한다. => 계속 정렬상태가 유지되는 듯 하다 => sort를 이용해서 계속 정렬을 진행하는 것보다 효율적이다!!

 

-여기서 pop과 top을 헷갈리면 안된다! 사실 내가 헷갈려서 pop으로 반환을 받았다..ㅎ

top()을 사용해 값을 반환받고, pop으로 삭제해야한다!

이것만 알면 어려운 문제는 아니기때문에

설명은 여기까지

 

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int new_sco=0;
    priority_queue <int, vector<int>, greater<int>> pq(scoville.begin(),scoville.end());
    int first_element=0;
    int second_element=0;
    while(pq.top()<K){
        if(pq.size()==1)
            return -1;
        
        first_element=pq.top();
        pq.pop();
        second_element=pq.top();
        pq.pop();
        
        new_sco=first_element+second_element*2;
        pq.push(new_sco);
        answer++;
    }
    
    
    return answer;
}