프로그래머스 : 더 맵게(C++, Lv.2, 힙)

https://programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

우선순위 큐에 대해 제대로 알지 못해 다른 풀이를 보고 풀었다.

• 정답 코드

#include <bits/stdc++.h>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    
    
    
    //오름차순 우선순위 큐 생성과 초기화 한 번에
//  priority_queue<int, vector<int>, greater<int>> pq(scoville.begin(), scoville.end());
    
    //오름차순 우선순위 큐 생성 방법
    priority_queue<int, vector<int>, greater<int>> pq;
    //스코빌 배열의 값을 우선 순위 큐에 전부 삽입
    for(auto v : scoville) {
        pq.push(v);
    }
    
    //큐 사이즈가 1보다 작지 않고 가장 낮은 스코빌이 K보다 작은 동안 횟수 증가
    while(pq.size() > 1 && pq.top() < K) {
        int a = pq.top();
        pq.pop();
        int b = pq.top();
        pq.pop();
        int c = a + b*2;
        pq.push(c);
        answer++;
    }
    if(pq.top() < K) return -1;
    else return answer;
}

---

• 처음 내가 푼 코드 (실패)

정답은 구해지지만 시간 복잡도를 고려하지 않아 맞추지 못하였다.

#include <bits/stdc++.h>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    sort(scoville.begin(), scoville.end());
    vector<int> new_scoville;
    while(scoville[0] < K) {
        
        int n = scoville[0] + scoville[1] *2;
        vector<int> new_scoville = {scoville.begin()+2, scoville.end()};
        new_scoville.push_back(n);
        sort(new_scoville.begin(), new_scoville.end());
        scoville = new_scoville;
        answer++;
    }
    
    return answer;
}

C++에서 힙을 구현하는 법을 까먹어서 찾아보니 우선순위 큐(priority_queue)로 구현해야 한다고 해서 빠르게 학습하고 다시 풀어보기로 했다.

https://koosaga.com/9

STL priority queue 활용법

---

• 2번 째로 푼 코드 (실패)

우선순위 큐를 익히고 아래 같이 풀었는데 16개 테케 중 4개가 시간 초과 났다...

아마 처음 큐 생성하는 데에 시간을 많이 써서 그런가 싶다

(알고보니 큐의 사이즈가 2보다 작은 경우 로직을 멈춰야 하는데 조건을 걸어주지 않아서 틀린거였다..)

걍 정답 코드를 보면서 익혀야겠다.

#include <bits/stdc++.h>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    
    priority_queue<int, vector<int>, greater<int>> pq;
    
    for(auto v : scoville) {
        pq.push(v);
    }
    
    while(pq.top() < K) {
        int a = pq.top();
        pq.pop();
        int b = pq.top();
        pq.pop();
        int c = a + b*2;
        pq.push(c);
        answer++;
    }
    if(answer == 0) return -1;
    else return answer;
}