백준 BOJ 14235 - 크리스마스 선물

우선순위큐를 죽어라 바이럴하는 문제

우선순위 큐(특히 STL의 그것) 에 대해 알고있다면 쉽게 해결할 수 있는 문제였다.

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

14235번: 크리스마스 선물

아이들이 요구할때마다 가장 가치가 큰 물건을 꺼내야 하기 때문에,

우선순위 큐를 통해서 우선순위(가치) 가 높은 숫자를 꺼내서 하나씩 출력해주면 된다.

 

굳이 우선순위 큐 아니더라도 중복 감안할수 있는 멀티셋 같은거 활용해도 되지 않나 싶기도 하고

아마 그냥 반복문으로도 해결을 할 수 있지 않을까 싶다.

정렬조차 안하는 기본적인 반복문으로도 문제 해결이 가능해서

아마 티어 내려야하지 싶다....

 

PQ를 사용한 풀이.

#include <bits/stdc++.h>
using namespace std;

priority_queue<int> pq;

int main(){
	int N,K,a;
	
	cin >> N;
	while(N--){
		cin >> K;
		if(!K){
			if(!pq.empty()){
				cout << pq.top() << "\n";
				pq.pop();
			}
			else{
				cout << -1 << "\n";
			}
		}
		else{
			for(int i=0; i<K; i++){
				cin >> a;
				pq.push(a);
			}
		}
	}
	return 0;
}

 

반복문을 사용한 풀이

#include <bits/stdc++.h>
using namespace std;

vector<int> v;

int main(){
	int N,K,a;
	
	cin >> N;
	while(N--){
		cin >> K;
		if(!K){
			int mx = -1;
			int mxptr = 0;
			for(int i=0; i<v.size(); i++){
				if(mx < v[i]){
					mx = v[i];
					mxptr = i;
				}
			}
			
			if(mx != -1){
				cout << mx << "\n";
				v[mxptr] = -1;
			}
			else{
				cout << -1 << "\n";
			}
		}
		else{
			for(int i=0; i<K; i++){
				cin >> a;
				v.push_back(a);
			}
		}
	}
	return 0;
}