[3주차] 백준 11279번: 최대 힙_C++

백준 11279: 최대 힙

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

11279번: 최대 힙

---

-> N을 입력받는다.

-> N개만큼 입력받는다.

-> 0이 아닌 자연수를 입력했을 경우에는 따로 출력없이 그냥 배열에 값을 넣어준다.

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

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

---

Priority_queue

-> 큐에 있는 모든 원소 중에서 가장 큰 값이 Top을 유지하도록, 우선순위가 가장 크도록 설계되어 있다.

// 우선순위 큐는 내부적으로 Heap이라는 자료구조를 사용하고 있음

 

- 선언방법

#include<queue>

priority_queue<자료형, 구현체, 비교연산자> pq;

 

- 기본적인 메소드

push(): 우선순위 큐에 원소를 추가한다

pop(): 우선순위 큐에서 top의 원소를 제거한다

top(): 우선순위 큐에서 top에 있는 원소 즉 우선순위가 높은 원소를 반환한다.

empty(): 우선순위 큐가 비어있으면 true를 반환하고 그렇지 않으면 false를 반환한다

size(): 우선순위 큐에 포함되어 있는 원소의 수를 반환한다

 

[참고] https://kbj96.tistory.com/15

https://jungeu1509.github.io/algorithm/use-priorityqueue/​

---

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


int main() {
	int N;
	priority_queue<int> pq;

	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() 등..)

?????????????? 

코드가 이렇게 간단한데 시간초과가 나오다니.. 

어떻게 수정해야할지 모르겠어서 for문을 while문으로도 바꿔보고 이것저것 해보다가 구글링했다. 

C++을 사용하고 있고 cin/cout을 사용하고자 한다면, cin.tie(NULL)과 sync_with_stdio(false)를 둘 다 적용해 주고, endl 대신 개행문자(\n)를 쓰자. 단, 이렇게 하면 더 이상 scanf/printf/puts/getchar/putchar 등 C의 입출력 방식을 사용하면 안 된다.

[시간초과가 나올 경우 대처법]  https://www.acmicpc.net/problem/15552

 

뭘 적용하라는데 뭔지 모르겠어서 더 구글링해보았다.

ios_base::sync_with_stdio 구문은 c의 stdio와 cpp의 iostream을 동기화시켜주는 역할을 하는데, 이 때 iostream과 stdio의 버퍼를 모두 사용하기 때문에 딜레이가 발생합니다. 따라서,ios_base::sync_with_stdio(false); 코드를 작성해줌으로써 동기화를 비활성화시켜줍니다.

cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
기본적으로 cin과 cout은 묶여있고 묶여있는 스트림들은 한 스트림이 다른 스트림에서 각 IO 작업을 진행하기 전에 자동으로 버퍼를 비워줌을 보장합니다. 

알고리즘을 풀 때는 보통 싱글 쓰레드 환경이기 때문에 ios_base::sync_with_stdio(false); 코드를 추가해줘도 결과에 영향이 없고 C와 C++의 버퍼를 분리하기 때문에 속도가 빨라집니다. (이때, c 스타일의 입출력문을 혼용하지 않도록 주의해줘야 합니다.)
기본적으로 cin으로 읽을 때 먼저 출력 버퍼를 비우는데, 마찬가지로 알고리즘을 풀 때는 화면에 바로 보이는 것이 중요하지 않습니다. 따라서, 입력과 출력을 여러 번 번갈아가며 반복해야 하는 경우 필수적으로 cin.tie(null); 코드를 추가하여 cout과 cin의 묶음을 풀어줘야 합니다.

[출처] https://jaimemin.tistory.com/1521 [꾸준함]

---

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


int main() {
	int N;
	priority_queue<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;
}

- 앞으로 문제 풀 때에는 c++ 코드를 작성할 때는 시간 초과를 경계하기 위해서는 cin.tie(NULL)을 통해 cout과 cin의 묶음을 풀어주자!

---

힘들다............................. 휴 

생각보다 문제를 풀 때 생각해야하는 점이 많은 것 같다 언젠가는 다 알 수 있으려나