프로그래머스 level 2 코딩 연습 -더 맵게

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

코딩테스트 연습 - 더 맵게 | 프로그래머스

정답: 

#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>> pri_Q;
    
   for(int i=0;i<scoville.size();i++){
      pri_Q.push(scoville[i]);
   }
   int sum=0;
   while(1){
        
        if(pri_Q.size()==1){
            return -1;
        }
        sum=sum+pri_Q.top();
        pri_Q.pop();
        sum=sum+pri_Q.top()*2;
        pri_Q.pop();
        pri_Q.push(sum);
       
        answer++;
        if(pri_Q.top()>=K){
           return answer; 
           //break;
        }
        sum=0;
    
        
        
    }
   
    

    //return 0;
}

200812

 

#include <string>
#include <vector>
#include <queue>
#include<iostream>
using namespace std;

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

     pq.push(total);
     
      answer++;
    if(pq.top()>=K)
    {
     
    
          return answer; 
        
    }
        
     total=0;
    }
  
    
    return answer;
}

지난번코드랑 별반 차이가 없음 

여기 핵심

queue와 prority_queue를 이용인데

순서에 따라 정렬된다.

트리구조를 이루고 있다.

그리고 큐와 스택과 달리 들어오는 순서가 아닌 숫자의 크기를 비교하여 push하면 그 순서에 맞게 정렬됨

pop하면 트리에 탑에 있는 값이 없어지며 다시 정렬되어 두번째로 정렬에 따른 순서로 나옴 

 priority_queue<int, vector<int>, greater<int> > pq;

greater에 경우에 작은숫자부터 큰순서로 트리형태로 정렬

less에 경우에는 큰숫자부터 작은 순으로 트리형태로 정렬

여기서 힙 정렬인 prority_queue를 사용한 이유는 첫번쨰 숫자와 다음 크기의 두번쨰 숫자의 push pop 관계이기에 priority queue를 사용한것이 효율적이다. 

 

201005 지난번과

 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성

 또 이번에도 이부분을 제대로 잘 못이해해서 조금 헤맷다

즉 모든 음식이다 그렇다면 prority queue는 트리 구조로 되어 잇고 작은순부터 가장 큰순이다 결국 가장 작은 값들이 스코필 지수가 올라가서 prority queue 들어가서 정렬되면 최종적으로 top이 가장 작은 값이므로 prority queue

top값만 검사해주면 모든 음식들이 스코필 지수 k이상이 되는셈이다. 

 

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

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