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

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

 

 

제한 사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

 

 

입출력 예

scovilleKreturn

[1, 2, 3, 9, 10, 12]

7

2

 

 

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int sum=0;
    
    
    if(sum>=k){
        
    sort(scoville.begin(), scoville.end());
    sum = scoville[0]+(scoville[1]*2);
    answer++;
        
    }else{
        
        return -1;
        
    }
    
    return answer;
}

부끄럽지만 처음에 적었던 코드.. 대충 무슨 말을 하려는지는 알겠는데

여기서 문제점은 queue를 쓰고도 내가 사용법을 제대로 인지하지 못했다는 것.

 

값을 사용하기 전, 사용한 후 제대로 pop/push 등을 통해 queue의 값을 처리해줘야 한다.

바로 '우선 순위 큐'

정렬을 위해 늘 sort를 쓰는 것이 답이 아니라는 것도 알게 되었다.

 

그리고 초기화 잊지 말기! queue 에 사이즈 만큼 push 해주어야 함.

queue 값 꺼내기 전 이동 후 pop하기도 참고....

 

 

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

using namespace std;

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

    
    return answer;
}

두번째 코드.. 정확성은 미미하고 효율성은 0로 나왔다.

 

 

 

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

using namespace std;

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

    
    return answer;
}

if-else로 늘리지 말고, while문을 사용하고 return -1은 if를 통해 한줄로 처리하였다.