[C++/알고리즘] 프로그래머스 (더 맵게)

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

코딩테스트 연습 - 더 맵게

 

처음에는 아무생각없이 vector sort를 이용해서 풀었다.

정확성 테스트는 통과했지만 효율성 테스트에서 빨간색 잔치가 열려서 당황했다가 이 문제가 heap 문제라는 것을 깨닫고 priority_queue를 이용해서 풀었다.

 

priority_queue를 이용하면서 뒤에 compare 조건으로 greater를 이용해 오름차순으로 정렬되게 만들었다.

그렇게 해서 top을 했을 때 작은 숫자가 나오는 것을 이용했다.

 

 

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

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

	for (int i = 0; i < scoville_size ; ++i)
	{
		t_scoville.push(scoville[i]);
	}

	while (1)
	{
		if (t_scoville.empty())
			return -1;

		if (t_scoville.size() == 1)
		{ 
			// 혹시 처음 조건 자체가 어떻게 될 지 모르니까 추가해 놓은 조건

			//음식이 하나인데 그 음식의 스코빌 지수가 K보다 작으면 -1
			if (t_scoville.top() < K)
				return -1;
		}

		// 가장 안 매운것 (temp_food1)과 그 다음으로 안 매운것(temp_food2)를 뽑아 스코빌 지수를 계산한다.
		auto temp_food1 = t_scoville.top();
		t_scoville.pop();
		auto temp_food2 = t_scoville.top();
		t_scoville.pop();

		int temp_scoville = temp_food1 + (temp_food2 * 2);

		t_scoville.push(temp_scoville);

		answer += 1;

		// 정렬된 상태의 scoville 지수. 만약 top의 값이 K보다 크다면 뒤의 것들은 당연히 더 클 것이므로 break한다.
		if (t_scoville.top() > K)
			break;
	}
	return answer;
}