C++ (코딩테스트) - 더 맵게(프로그래머스)

실패한 코드

 

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

void swap(int *x, int *y) {
	int temp = *x;
	*x = *y;
	*y = temp;
}

int solution(vector<int> scoville, int K) {
	int answer = 0;
	
	sort(scoville.begin(), scoville.end());

	for (int i = 0; i < scoville.size() - 1; i++)
	{
		if (scoville[i] < K)
		{
			scoville[i + 1] = scoville[i] + 2 * scoville[i + 1];
			answer++;

			int j = i;
			while (j + 2 != scoville.size())
			{
				if (scoville[j + 1] > scoville[j + 2])
				{
					swap(scoville[j + 1], scoville[j + 2]);
					j++;
				}
				else
					break;
			}
			scoville.erase(scoville.begin() + i, scoville.begin() + i + 1);
			i--;
		}
	}
	if (scoville.back() < K) return -1;

	return answer;
}

 

 

수정후 priority_queue를 사용하자..

 

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

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

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

    for (auto & v : scoville) pq.push(v);

    while (true)
    {
        if (pq.size() == 1)
        {
            if (pq.top() < K) return -1;
            return answer;
        }
        else if(pq.top()<K)
        {
            int sum = pq.top();
            pq.pop();
            sum += 2 * pq.top();
            pq.pop();
            pq.push(sum);
            answer++;           
        }
        else return answer;
    }
    return answer;
}