[백준] 1927 최소 힙 [C++]

처음에 힙을 직접 구현해서 풀었는데, 시간초과를 해결하지 못하고 결국 C++ STL 컨테이너 priority_queue를 사용하였다.

priority_queue [C++ / STL 컨테이너 ]

c++의 컨테이너 어댑터로, vector 클래스의 인터페이스를 제한하여 만든 컨테이너이다. 디폴트로 less operator를 사용하여 데이터가 내림차순 정렬되어 최대 힙으로 두현된다. greater operator를 사용하면 데이터를 오름차순으로 저장할 수 있어, 최소 힙 구현이 가능하다.

**헤더파일**
#include <queue>		// priority_queue 포함
#include <functional>	// less와 greater를 사용하기 위해 선언

핵심 메소드

push() : 우선순위 큐에 원소를 추가한다
pop() : 우선순위 큐에서 top의 원소를 제거한다
top() : 우선순위 큐에서 top에 있는 원소 즉 우선순위가 높은 원소를 반환한다
empty() : 우선순위 큐가 비어있으면 true, 그렇지 않으면 false를 반환한다
size() : 우선순위 큐에 포함되어 있는 원소의 수를 반환한다

그래도 시간초과??

priority_queue를 이용하였는데도 시간초과가 났다. 구글링을 해본 결과, 코드에

cin.tie(NULL);
ios_base::sync_with_stdio(false);

이 두 줄을 추가하여 해결하였다.

위 표를 보면 알 수 있듯이 cin이 scanf에 비해 2.5배정도 느리다. 이것은 c++의 입출력스트림에서 iostream의 버퍼와 stdio의 버퍼를 모두 사용해 동기화 하는 과정 때문인데, ios_base::sync_with_stdio(false); 이 코드를 추가해주면 동기화를 해제해 stdio의 버퍼를 사용하지 않아 속도가 향상된다.
*주의할 점은 이 방법은 싱글스레드 환경에만 사용해야 하고, 멀티스레드 환경에서 사용하면 안된다. 어짜피 알고리즘 문제를 푸는 것은 싱글스레드이기 때문에 상관없긴 하다. 알고리즘 문제풀 때만 쓰기.

전체 코드

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

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int N = 0, input = 0;
	priority_queue<int, vector<int>, greater<int>> pq;		//우선순위 큐 객체 생성
	cin >> N;		//총 연산 수
	
	for (int i = 0; i < N; i++) {
		cin >> input;
		if (input != 0) {		//입력값이 0이 아니면 우선순위 큐에 값 삽입
			pq.push(input);
		}
		else {					//입력값이 0이면 우선순위 큐에서 값 pop
			if (pq.size() == 0) {		//힙이 비어있을 때는 0 출력
				cout << 0 << "\n";
			}
			else {
				cout << pq.top() << "\n";		//루트에 있는 값 반환
				pq.pop();				//루트에 있는 값 삭제
			}
		}
	}
	return 0;
}