프로그래머스 더 맵게

1. 프로그래머스 더 맵게 문제

2. 컴퓨팅적 스킬

• 이번 문제를 해결하기 위해서는 단순 sort를 사용하는것이 아니라 우선순위큐 priority_queue<int,vector<int>,greater<int>> 오름차순 형식으로 써주어야합니다.
• 단순히 while문을 통해서 안에서 sort를 처리하려고 하였지만 16번 테스트케이스를 통과하지 못하였고 효율성에서는 시간초과가 발생하였습니다. 또한, 범위값이 너무 제한적이였다. 그래서 우선순위큐를 사용하였습니다.

scoville의 길이는 1 이상 1,000,000 이하입니다.
K는 0 이상 1,000,000,000 이하입니다.
scoville의 원소는 각각 0 이상 1,000,000 이하입니다.

• 주의해야할점은 우선순위큐 push는 맨앞으로 들어간다는것과 top에 있는것도 0번째 인덱스에 있는 값입니다.

---

3. 컴퓨팅적 사고

1. 스코빌 벡터에 있는 값을 우선순위큐에 넣어준다. greater<int>를 옵션으로 지정하였기 때문에 자동으로 오름차순으로 정렬해줍니다. 만약 내림차순으로 하고 싶은경우 less옵션을 사용하시면 됩니다.
2. 첫번째, 두번째값을 통하여 스코빌 지수를 구합니다. 단 q.top()의 값이 K보다 작아야합니다. 반복문 조건

예시
스코빌 1 2 3 9 10일경우  
(1 + 2 * 2) 5 3 9 10 으로 변경됩니다. 우선순위큐 이므로 3 5 9 10 정렬됩니다.
(3 + 5 * 2) 13 9 10 으로 변경됩니다. 우선순위큐 이므로 9 10 13 정렬됩니다.
......

3. 기존의 while문에서는 sort를 다시해주어야하는데 우선순위 큐가 자동으로 정렬시켜주기때문에 필요없는 과정입니다.
4. 만약 우선순위큐의 사이즈가 2이하가 되면 더이상 구할 수 없으므로 Return -1을 실행합니다. 그게 아니라면 계속 진행하고 q.top()의 값이 K보다 큰 경우가 있으면 더이상 반복문을 반복하지 않습니다.

---

4. 풀이

4.1. 1. 일반적인 sort 풀이(시간초과)

//
//  더맵게 일반 정렬.cpp
//  algorithm-level-up
//
//  Created by kgh on 20/11/2019.
//  Copyright © 2019 kgh. All rights reserved.
//
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void){
    vector<int> scoville;
  
    scoville.push_back(3);
    scoville.push_back(9);
    scoville.push_back(10);
    scoville.push_back(12);
    int K=7;
    int cnt = 0;
    int answer = 0;
    int len = scoville.size();
    while(true){
        
        sort(scoville.begin(),scoville.end());
        // 스코빌 첫번째 값이 K보다 작아야하고, cnt 값이 해당 스코빌 사이즈값이전까지 돌아아한다, 그리고 스코빌 사이즈는 2보다 커야한다. 아니면 -> 메모리 에러남
        if(scoville[0] < K && cnt < len && scoville.size() > 2){
            int new_scoville=0;
                  
          new_scoville = scoville[0] + (scoville[1] * 2);
          scoville[0] = new_scoville;
          scoville.erase(scoville.begin()+1);
          cnt+=1;
            
        }else {
            // 스코빌 첫번째지수가 K보다 작으면 결국 모든것이 되지않았으니까 cnt = 0;
            if(scoville[0] < K){
                cnt = 0;
            }
            break;
        }
      
    }
    
    if(cnt == 0){
        answer = -1;
        cout << answer;
    }else {
        answer = cnt;
        cout << answer;
    }
    
    return 0;
}

4.2. 우선순위큐 사용

//
//  더맵게 우선순위큐.cpp
//  algorithm-level-up
//
//  Created by kgh on 20/11/2019.
//  Copyright © 2019 kgh. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <queue>

using namespace std;
int main(void){
    vector<int> scoville;
    scoville.push_back(1);
    scoville.push_back(2);
    scoville.push_back(3);
    scoville.push_back(9);
    scoville.push_back(10);
    scoville.push_back(12);
    priority_queue<int,vector<int>,greater<int>> q;
    int K = 7;
    for(int i=0; i<scoville.size(); i++){
        q.push(scoville[i]);
    }
    
    
    int min_num_first = 0;
    int min_num_second = 0;
    int res = 0;
    int cnt = 0;
    while(q.top() < K){
        
        if(q.size() < 2){
            return -1;
        }
        
        min_num_first = q.top();
        q.pop();
        min_num_second = q.top();
        q.pop();
        
        res = min_num_first + (min_num_second * 2);
        q.push(res);
        cnt += 1;
    }
    cout << cnt;
}