[프로그래머스] 더맵게

문제 요약

1. 모든 음식의 맵기 지수가 K 이상이 되려면 몇 번 섞어야 할까요?
2. 레오가 음식을 섞는 기준
   1) 지수가 낮은 순으로 1등과 2등을 뽑아 섞는다.
   2) 섞은 음식 지수 = 가장 낮은 지수+ 2* 2번째로 낮은 지수

방심

1. 우선순위 큐 문제인데 그냥 queue로 정의 해버렸다.
   심지어 습관상 top을 썼는데 에러나길래 fornt()로 바꿔준것이애오^^
2. 반복문 한 번 돌 때마다 2개씩 뽑아서 섞고 넣어줬는데
   첫번째 거 뽑고 pop()을 하기 전에 2번째 걸 뽑아도 되는지(q.empty())검사했다.ㅋㅋㅋ..ㅋ.ㅋ.. 그러니까 pq가 [5] 만 들어있는 상태면
   5를 먼저 뽑아놓고 유령 5가 남아있어서 더 뽑아도 되겠지 하면서 언더플로우가 발생한다..

그래도 잘한 점

1. 기준치 스코빌 지수가 10^9까지이긴 하지만 연산과정 중에 int 범위를 넘을 수 있음을 간파하고 long long int로 해줬다

코드

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

using namespace std;
struct comp{
    bool operator() (long long int &a, long long int &b){
        return a>b;
    }
};

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<long long int,vector<long long int>,comp> q;//항상 가장 작은거
    for(int i = 0;i<scoville.size();i++){
        q.push(scoville[i]);
    }
    bool reachable = false;
    int ctr = 0;//int 범위에서 될 것
    while(!q.empty()){//하나 남았을 때 문제 생길 수 있음
        long long int a = q.top();
        q.pop();
        if(a>=K){//목표 달성
            reachable = true;
            break;
        }
        if(q.empty()){//하나남았을 때
            break;
        }
        long long int b = q.top();
        q.pop();
        long long int new_food = a + 2 * b;
        //cout<<a<<", "<<b<<","<<new_food<<endl;
        q.push(new_food);
        //cout<<"pushing "<<new_food<<endl;
        ctr++;
    }
    if(!reachable){
        answer = -1;
    }
    else{
        answer = ctr;
    }
    return answer;
}

2021/05/05 2트

방심했던것

long long int queue에서 뽑은 걸 int로 캐스팅

• 스코빌 지수를 섞다보면 3*k 정도의 스코빌 지수가 들어갈 수도 있다는 것을 알고 있었다. 그래서 queue는 long long int를 원소로 갖도록 만들어놨는데 습관적으로 int 로 downcasting해버렸다.. 내가 옛날에 만들어 둔 테스트케이스가 없었다면 고대로 틀려버렸겠지

큐사이즈가 2이하로 떨어지는 경우에 대해 구현을 안했음

한번의 섞기 연산에 2개의 음식이 필요하므로 while문에는 2개가 있을때라는 조건을 걸었다.
음식 수가 2개이상 남은 상황에서 k가 만들어지면 괜찮지만 극단적으로 예를 들었을 때,

음식들 : [3,5] , k :10 이런 상황이 생길 수 있다.
이 때 3, 5를 섞어서 13 하나만 queue(size : 1)에 들어가 있는 상황에서
while문을 탈출하고 queue의 top인 13은 무시당하게 된다.

#include <string>
#include <vector>
#include<queue>
#include<iostream>
using namespace std;
//3K 정도 예상해야하므로 long long
struct comp{
    bool operator()(long long int &a, long long int &b){
        return a>b;//sort와 다르게 반대로 함
    }
};

int solution(vector<int> scoville, int K) {
    int answer = -1;
    priority_queue<long long int,vector<long long int>, comp> q;
    for(int i = 0;i<scoville.size();i++){
        q.push(scoville[i]);
    }
    int num = 0;
    while(q.size()>=2){
        long long int a = q.top();
        q.pop();
        long long int b = q.top();
        //cout<<a<<","<<b<< ","<<a+b*2<<endl;
        q.pop();
        if(a>=K){
            answer = num;
            break;
        }
        num++;
        q.push(a+b*2);
    }
    if(q.size()==1){
        if(q.top()>=K){
            //cout<<"1개만 남았을 때 :"<<q.size()<<" , "<<q.top()<<endl;
            answer = num;
        }
    }
    return answer;
}