[Baekjoon] 11279번 최대 힙(C++)

 

www.acmicpc.net/problem/11279

11279번: 최대 힙

 

Level: Level 1

풀이: 유사문제 참고

Language: C++

 

 

문제 설명

널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.

2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

 

 

입력/출력

입력

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다.

입력 예

13 0 1 2 0 0 3 2 1 0 0 0 0 0

출력

입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.

출력 예

0 2 1 3 2 1 0 0

 

 

풀이

힙 Heap): 쌓아 올린 더미

최대 힙은 부모 값이 항상 자식 값보다 커야 한다.

유사문제를 보고 힌트를 얻었다.

C++ 표준 라이브러리에서 제공하는 priority_queue를 사용하면 쉽게 해결할 수 있다.

⇒ 우선순위 큐를 구현한 것

⇒ <queue> 헤더 파일

⇒ void pop() 맨 위에 있는 인자를 삭제한다.

⇒ void push (const value_type& val) 인자를 삽입한다.

 

출력 값이 입력 값과 같이 나온다.

 

Code

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<queue>

using namespace std;

int n;//연산의 개수
priority_queue<int> q;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		if (x == 0) {
			if (q.empty())
				cout << "0\n";
			else {
				cout << q.top() << "\n";
				q.pop();
				//queue의 FIFO 성질
			}
		}
		else
			q.push(x);//queue에 삽입
	}
	return 0;
}

 

ScreenShot

 

출처

blockdmask.tistory.com/107

[C++] priority_queue container 정리 및 사용법