글 읽기 - c++ 최대힙 구현 시간초과 도와주세요 (주석있습니다)

swinnovator 2년 전 0

반례도 다 넣어봤는데 맞게 출력이 되어서

어느 부분 때문에 시간초과가 발생하는지 궁금합니다.

//#define TEST

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

template <typename T> class MaxHeap{
	private:
		T *heap;
		int capacity;
		int heapSize;
	public:
		MaxHeap(int capacity);
		~MaxHeap();
		bool empty();
		void push(T element);
		void pop();
		void print();
		T top();
};

int main() {
	#ifdef TEST
	freopen("input1.txt", "r", stdin);
	#endif

	MaxHeap<int> maxheap(100000);

	int op_size;
	cin >> op_size;


	while(op_size--){
		int element;
		cin >> element;

		if(element == 0){
			if(maxheap.empty()){
				cout << "0" << '\n';
			}
			else{
				cout << maxheap.top() << '\n';
				maxheap.pop();
			}
		}
		else{
			maxheap.push(element);
		}
	}

	#ifdef TEST
	fclose(stdin);
	#endif
	return 0;
}

template<typename T> MaxHeap<T>::MaxHeap(int capacity){
	this->capacity = capacity;
	heap = new T[capacity];
	heapSize = 0;
	heap[0] = -1;
}

template<typename T> MaxHeap<T>::~MaxHeap(){
	delete[] heap;
}

template<typename T> void MaxHeap<T>::push(T element){
	heapSize++;
	//[1] 마지막 인덱스에 원소 삽입
	heap[heapSize] = element;

	//[2] 최대힙의 조건(부모노드 >= 자식노드)에 맞게 힙 재정렬(swap)
	int idx = heapSize;
    //루트 노드 이거나, 조건을 만족할 경우
	while((idx != 1) && (heap[idx/2] <= heap[idx])){ 
		swap(heap[idx], heap[idx/2]);
		idx /= 2;
	}
}

template<typename T> void MaxHeap<T>::pop(){
	//[1] 루트노드를 pop하고 마지막 노드를 루트 노드로 올린다.
	heap[1] = heap[heapSize];
	heapSize--;	

	//[2] 루트노드에서 부터 자식노드와 swap하며 힙 재정렬
	int idx = 1;

	while(idx <= heapSize){
		
		int leftIdx = idx*2;
		int rightIdx = idx*2+1;

		// [2-1] 둘다 heap범위 만족
		if((leftIdx <= heapSize) && (rightIdx <= heapSize)){
			// [2-1-1] 왼쪽 자식이 오른쪽 자식보다 크고, 부모보다도 크면
			if((heap[leftIdx] >= heap[rightIdx]) && (heap[leftIdx] > heap[idx])) {
				swap(heap[leftIdx], heap[idx]);
				idx = leftIdx;
			}
			// [2-1-2] 오른쪽 자식이 왼쪽 자식보다 크고, 부모보다도 크면
			else if((heap[leftIdx] < heap[rightIdx]) && (heap[rightIdx] > heap[idx])){ 
				swap(heap[rightIdx], heap[idx]);
				idx = rightIdx;
			}
			else break;
		}
		// [2-2] 왼쪽 자식만 heap 범위 만족
		else if((leftIdx <= heapSize) && (rightIdx > heapSize)){
			if(heap[leftIdx] > heap[idx]){
				swap(heap[leftIdx], heap[idx]);
				idx = leftIdx;
			}
			else break;
		}
		// [2-3] 오른쪽 자식만 heap 범위 만족
		else if((rightIdx <= heapSize) && (leftIdx > heapSize)) {
			if(heap[rightIdx] > heap[idx]){
				swap(heap[rightIdx], heap[idx]);
				idx = rightIdx;
			}
			else break;
		}
		else break;
	}
}

template<typename T> void MaxHeap<T>::print(){
	cout << "heap[] = {";
	for(int i = 1 ; i <= heapSize ;i++){
		cout << heap[i] << ", ";
	}
	cout << "}\n";
}

template<typename T> T MaxHeap<T>::top(){
	return heap[1];	// 루트 노드 리턴
}

template<typename T> bool MaxHeap<T>::empty(){
	return this->heapSize == 0;
}

adfsfsf 2년 전 1

입출력을 할 때 cin, cout을 쓰신 게 문제인 것 같습니다. 웬만하면 scanf, printf를 쓰라고 하더라고요.그런데 테스트 케이스 이름이 안 나오는데 파일 열기 방식으로 입출력이 되나요? 그냥 입력받는 걸로 아는데요.

swinnovator 2년 전 1

freopen 으로 txt 파일에 예제를 넣어두고 했습니다

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

를 추가하고 scanf, printf 를 쓰니깐 시간초과에 안걸리네요

감사합니다!

baksa1849 2년 전 0

ios_base::sync_with_stdio(false);

cin.tie(NULL);

은 cin, cout을 이용한 빠른 입출력을 쓸 때 이용합니다.

scanf와 printf는 그 자체로 충분히 빠릅니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c++ 최대힙 구현 시간초과 도와주세요 (주석있습니다)

swinnovator 2년 전 0

adfsfsf 2년 전 1

swinnovator 2년 전 1

baksa1849 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말