[BOJ] 1927_최소 힙

최소 힙

문제 링크: https://www.acmicpc.net/problem/1927

간단한 자료구조 priority_queue를 사용하는 방법에 대한 문제이다.
다만 c++로 그냥 사용하면 시간초과가 나오는게 이 문제의 핵심이다.

 

c로 작성해서 제출하면 아마 정답이라고 나올것이다.
즉, 알고리즘 적으로 문제가 있는 것이 아니라, c++의 표준 입출력의 문제가 있는 것이다.

 

해당 문제의 질문들을 둘러보았다.
https://www.acmicpc.net/board/view/33074

여기에 따르면, c++은 기본적으로 입출력 작업을 할 때마다 c의 표준 입출력과 동기화되어 있도록 설정이 되어있다고 한다.
또한, 마지막으로 작업한 I/O 스트림이 아닌 다른 곳에서 입출력 작업을 하려고 할 때 입출력 버퍼를 비우는 작업을 수행하는 작업들이 입출력 시간을 늘린다고 한다.

 

그래서 다음과 같은 코드들을 추가해주어 동기화를 시키지 않고, 버퍼를 자동으로 비우지 않도록 하면 정답으로 처리가 된다.

ios_base::sync_with_stdio(false); : c와 표준 입출력과의 동기화를 하지 않도록 설정한다.
cin.tie(NULL); cout.tie(NULL); : 자동으로 스트림을 untie 시켜 자동으로 입출력 버퍼를 비우지 않도록 설정한다.

 

• 정답 코드

   

• #include<iostream>
  #include<queue>
  using namespace std;
  
  int main() {
  	ios_base::sync_with_stdio(false);
  	cin.tie(NULL); cout.tie(NULL); 
  	priority_queue<int, vector<int>,greater<int>> T;
  	
  	int n;
  	cin >> n;
  	
  	while (n--) {
  		int i;
  		cin >> i;
  		if (i != 0)
  			T.push(i);
  		else {
  			if (!T.empty()) {
  				printf("%d", T.top());
  				T.pop();
  			}
  			else
  				printf("%d",0);
  			printf("\n");
  		}
  	}
  
  	return 0;
  }