[6주차] 백준 1927번: 최소 힙_C++

백준 1927: 최소 힙

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

1927번: 최소 힙

---

-> 배열의 크기 N을 입력받는다.

-> 배열에 대한 정보 값 x를 입력받는다. 

-> x가 0이 아닌 자연수일 경우에는 배열에 그 값을 추가해준다

-> 0을 입력했다면 배열에서 가장 작은 수를 출력해주고,그 값을 제거해준다.

// 단, 배열에 값이 없을 경우는 0을 출력해준다

---

보자마자 전에 풀었던 최대 힙과 매~~~~~우 비슷한 것 같았다.

중요한 것은 전에는 가장 큰 수가 top에 오게 하는 내림차순 배열이었다면, 

이번에는 작은수가 top에 오게하는 오름차순 배열이라는 것이다! (참고로 default가 내림차순임)

그런데 공부를 제대로 안해서..인지 오름차순 배열을 선언하는 법을 모르겠어서 구글링했다.

 

---

최대 힙: https://mnzy.tistory.com/manage/newpost/17?type=post&returnURL=https%3A%2F%2Fmnzy.tistory.com%2F17%3Fcategory%3D1010434

 

오름차순 배열 선언 참고: https://ssinee.tistory.com/entry/%EB%B0%B1%EC%A4%801927%EB%B2%88-%EC%B5%9C%EC%86%8C-%ED%9E%99?category=440812 

 priority_queue 오름차순 배열 선언: priority_queue<int, vector<int>, greater<int>> pq;

// 정확히 왜 저러는 건지 모르겠음.. 나중에 제대로 찾아보고 공부 예정

---

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

int main() {
	int N;
	priority_queue<int, vector<int>, greater<int>> pq;
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> N;

	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;

		if (x == 0) {
			if (pq.empty()) {
				cout << 0 << "\n";
			}
			else {
				cout << pq.top() << "\n";
				pq.pop();
			}
		}
		else {
			pq.push(x);
		}
	}
	return 0;

-> for문을 통해서 N번 반복할 수 있게 해주었고 if문을 통해 0과 관련된 조건들을 만족시켜주었다.

-> 함수들은 queue라이브러리 내장 함수 이용(top(),pop() 등..)

 

---

오름차순 배열 선언을 제외하고는 최대 힙(https://mnzy.tistory.com/manage/newpost/17?type=post&returnURL=https%3A%2F%2Fmnzy.tistory.com%2F17%3Fcategory%3D1010434) 과 크게 다를 것이 없어서

쉽게 해결할 수 있었다!