작은시작

문제

https://www.acmicpc.net/problem/11279

풀이

기본 최대 힙 구성 문제였다.

C++의 Priority_queue 를 활용하였다.

최소힙 문법 문제는 아래를 참고하자. 

https://trevor522.tistory.com/89

코드

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
priority_queue<int> pq;
vector<int> result;
int  main() {
	int N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		if (a == 0) {
			if (pq.empty()) {
				result.push_back(0);
			}
			else {
				result.push_back(pq.top());
				pq.pop();
			}


		}
		else {
			pq.push(a);
		}
		



	}
	for (int j = 0; j < result.size(); j++) {
		cout << result[j] << '\n';

	}



	return 0;
}

문제

https://www.acmicpc.net/problem/1927

풀이

최소힙 기본연습문제이다. 

C++ 의 Priority_queue를 활용하였다. 

최소 힙 같은경우  priority_queue<int,vector<int>,greater<int>> 를 사용하면 된다. 

코드

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

priority_queue<int, vector<int>, greater<>> pq;
vector<int> result;
int  main() {
	int N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		if (a == 0) {
			if (pq.empty()) {
				result.push_back(0);
			}
			else {
				result.push_back(pq.top());
				pq.pop();
			}


		}
		else {
			pq.push(a);
		}
		



	}
	for (int j = 0; j < result.size(); j++) {
		cout << result[j] << '\n';

	}



	return 0;
}

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

코드설명

처음에는 K값이 이렇게 큰줄 모르고 단순 구현하였다... (scoville 벡터를 매번 sort하고 erase,push_back) 방식으로..

하지만 당연히 효율성에서 시간초과가 났고 아차싶었다

우선수위큐(minHeap)을 통해 O(N)으로 코드를 다시 짰다. 

그리고 pop()을 두번 하는과정이 있기때문에 중간에 큐가 빈건 아닌지 꼭 한번더 체크하자!!!!!!!!!!!!!!!!!!!!!!!

안하면 core dumped

코드

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

using namespace std;


priority_queue<int,vector<int>,greater<int>> pq;
int solution(vector<int> scoville, int K) {
    int answer = 0;
    
    for(int i=0;i<scoville.size();i++){
        pq.push(scoville[i]);
    
    }
    int cnt=0;
    while(pq.top() < K && !pq.empty()){
        int temp=pq.top();
        pq.pop();
        temp=temp+pq.top()*2;
        if(pq.empty()) break;
        pq.pop();
        pq.push(temp);
        cnt++;
    }
    if(pq.empty()) answer=-1;
    else{
        answer=cnt;
    }
    
    
    return answer;
}