프로그래머스 LV.2 더 맵게

 
 

 
이 문제는 간단한 예외처리 요하므로
예외처리를 할 게 딱히 많지 않다.

예외 처리의 경우

1. scoville의 size()가 2보다 작은 경우에는 비교를 할 수 없다.
그 경우에는 K보다 작은지만 체크해 준 뒤 -1을 반환하면 된다.

전반적인 로직 간략 설명

1. 가장 작은 스코빌 지수 + (두 번째로 작은 스코빌 지수 * 2)는
힙을 사용한 우선순위 큐로 관리할 수 있다.
 
1. 작은 스코빌 지수는 자동으로 정렬이 되므로,
top으로 읽어온 뒤 해당 값을 임시로 저장해둔다.
 
2. pop을 통해 작은 값을 꺼내 준뒤 
그 2번째 값을 top으로 읽어온 뒤
임시 저장 값에 += 두 번째 * 2 라는 로직을 추가해준다.
이후 pop해주기
 
3. 임시 저장 값을 우선순위 큐에 넣어주면 자동 정렬된다.
 
위 과정을 조건이 만족할 때 까지 반복하면 된다.
 

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

using namespace std;

struct cmp {
    bool operator()(int a, int b) {
        return a > b;
    }
};

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int first;

    priority_queue<int,vector<int>, cmp> q;

    for (int s : scoville) {
        q.push(s);
    }

    while (q.size() > 1)
    {
        if (q.top() >= K) break;
        
        first = q.top(); 
        q.pop();
        first += q.top() * 2;
        q.pop();
        q.push(first);

        answer++;
    }

    if (q.top() < K) return -1;

    return answer;
}

 
효율성 테스트