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

문제 풀이

 

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    
    // 우선순위 큐를 사용. 오름차순으로 사용하기 위해 greater<int> 추가
    priority_queue<int, vector<int>, greater<int>> pq;
    
    // 우선순위 큐에 scovile 값을 넣는다. auto는 파이썬의 for i in array와 같은 표현이라고 생각하면 된다.
	for (auto it : scoville)
		pq.push(it);

	while (1) {
    	// 첫 번째 원소를 가져온 후 pop한다.
		int first = pq.top(); 
		pq.pop();
        
        // pq를 다 돌았음에도 스코빌 지수가 충족되지 않는다면 -1을 리턴한다.
		if (pq.size() < 1 && first < K) return -1;
		
        // 스코빌 지수를 충족시켰다면 while문을 탈출한다. 여기서 return answer를 해도 상관없다.
		if (first >= K)	break;
		
        // 아직 스코빌 지수를 충족시키지 못한 상태라면
		else {
        	// 두 번재 원소를 가져온 후 스코빌 공식을 사용한다.
			int second = pq.top(); 
			int mix = first + second * 2;
            
            // 이후 사용한 두번째 원소를 뺀 뒤 섞은 원소를 삽입한다.
			pq.pop();
			pq.push(mix);
            answer++;
		}
	}
    
    return answer;
}

 

 

 

문제 링크

 

 

programmers.co.kr/learn/courses/30/lessons/42626?language=cpp

코딩테스트 연습 - 더 맵게