[프로그래머스 Lv2] - 더 맵게

19 May 2021

Reading time ~1 minute

복기

힙 문제이지만 문제해결방법을 제대로 찾지 못해 재귀로 풀려고 했음
몇몇 테스트는 통과했지만 Segmentation Fault가 났고 시간초과 발생
이 문제는 재귀로 풀면 안된다는 뜻

내가 작성한 코드(실패)

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool compare (int a, int b){
    if(a<b){
        return true;
    }else{
        return false;
    }
}

void recur(vector<int> scoville, int K, int& count){

    sort(scoville.begin(), scoville.end(), compare);
    scoville[0]=scoville[0] + scoville[1]*2; // scoville[0]을 새로운 스코빌 지수로 변환 
    scoville.erase(scoville.begin()+2);

    
    for(int i=0; i<scoville.size(); i++){
        if(scoville[i]<K){
            count++;
            recur(scoville, K, count);
            break;       
        }
    }

    
}

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int count=0;
    if(scoville.size()==1 && scoville[0]<K){
        return -1;
    }
    recur(scoville, K, count);
    answer=count;
    return answer;
}

큐를 이용한 풀이

우선순위 큐 선언방식 암기
priority_queue<T, Container, Compare>: 원하는 자료형 및 클래스 T를 통해 생성. 여기서 Container는 vector와 같은 컨테이너이며 Compare는 비교함수 클래스

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    
    priority_queue<int,vector<int>,greater<int>> temp;
    for(int i=0;i<scoville.size();i++)
        temp.push(scoville[i]);
 
    while (temp.top() < K && temp.size()>1) {
        int first,second;
        answer++;
        first = temp.top(); temp.pop();
        second = temp.top(); temp.pop();
        temp.push(first + second * 2);
    }
    if (temp.top() < K)
        return -1;
    return answer;
}