[프로그래머스 Level2 힙] 더 맵게

문제

입출력

문제풀이

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int i = 0;
    while(1){    
        sort(scoville.begin(), scoville.end());//정렬

        if(scoville[i] >= K){
            break;
        }
        else {
            answer++;
            int new_input = scoville[i] + (scoville[i+1] * 2);
            scoville.erase(scoville.begin(),scoville.begin()+2);//
            //scoville.erase(scoville.begin()+1);
            scoville.push_back(new_input);
        }
        }
    return answer;
}
//스코빌 지수를 K 이상으로 만들기 위해 leo는 스코빌 지수가 가장 낮은 두개의 음식을 아래와 같이 특별한 방법으로 섞어 
//가장 맵지 않은 음식 + 두번째 * 2 : k이상이 될때까지. 반복
//배열과 원하는 K에서 횟수.

vector STL로 풀 수 있을거라 생각했다.

하지만 vector.erase 를 잘 못 생각해서 answer 결과값이 +1 더해져 나와, erase 구글링..

시작지점 이상 ~ 끝 지점 미만을 지우는 것이다.

하지만 vector로 풀었더니 시간초과로 실패. 

 

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional> //greator
#include <iostream>
using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int i = 0;
    
    priority_queue <int, vector<int>, greater<int>> pq;
    int size = scoville.size();
    
    //pq에 넣기
    for(int i =0;i<size;i++){
        pq.push(scoville[i]);
    }
    
    while(1){
        //K보다 작은 경우
        if(pq.size() == 1 && pq.top() < K){
            return -1;
        }      
        else if(pq.top() < K){
            //두개 빼기
            int first = pq.top();
            pq.pop();
            int second = pq.top();
            pq.pop();
            //넣기
            int new_item = first + second*2;
            pq.push(new_item);
            answer++;
        }
        else {
            break;
        }
    }

    return answer;
}
//스코빌 지수를 K 이상으로 만들기 위해 leo는 스코빌 지수가 가장 낮은 두개의 음식을 아래와 같이 특별한 방법으로 섞어 
//가장 맵지 않은 음식 + 두번째 * 2 : k이상이 될때까지. 반복
//배열과 원하는 K에서 횟수.

예외처리를 하느라 애 좀 먹었다.

(1) 모든 원소값이 K이상으로 더해지지 않는 경우 return -1하기

(2) K값 이상으로 되는 상황이 size() == 1인 경우

 

우선순위큐 오름차순 처음 써봤다. greater, <functional> 기억!