글 읽기 - 샘플은 맞았으나 어떤 부분때문에 런타임 에러가 났는지 궁금합니다.

kangsy763 4년 전 0

절대값이 아닌 최소힙 최대힙 문제때에는 런타임 에러가 나지 않았는데, 이 경우에는 런타임 에러가 났습니다.

배열 때문에 난거는 아닌 것 같은데... (맞나...)

무엇이 문제를 일으켰는지 알고 싶습니다

#include <stdio.h>
#include <cstdlib>
#define swap(a,b){int tmp;tmp=a,a=b,b=tmp;}
using namespace std;

int heap[100001];						//힙 배열
int h_cnt = 0;							//힙 카운트

void insert(int n) {
	heap[++h_cnt] = n;
	int child = h_cnt;
	int parent = child / 2;
	while (abs(heap[child]) <= abs(heap[parent]) && parent >=1) {			//절대값 이하로 조건 걸었다.
		if (abs(heap[child]) == abs(heap[parent]) && heap[child] < heap[parent]) {		//절대값 같은 경우에 일반 값 비교해본다.
			swap(heap[child], heap[parent]);
		}
		else if (abs(heap[child]) == abs(heap[parent]) && heap[child] >= heap[parent]) break;	//일반 값이 큰 경우엔 break했다.
		else if (abs(heap[child]) < abs(heap[parent])) {			//절대값 다른 경우엔 절대값 비교해서 최소힙으로 했다.
			swap(heap[child], heap[parent]);
		}
		child = parent;
		parent = child / 2;
	}
}

int pop() {
	if (h_cnt == 0) return 0;
	int result = heap[1];
	swap(heap[1], heap[h_cnt]);	// 1 과 h_cnt 끝 값을 교환 해주었다.
	heap[h_cnt] = 0;			//그냥 삭제하고 0으로 넣어주었다. 
	h_cnt--;
	int parent = 1;
	int child = parent * 2;
	if (child + 1 <= h_cnt) {
		if (abs(heap[child]) == abs(heap[child + 1])) {		//이 경우에도 절대값 같으면 일반 값 비교
			child = (heap[child] < heap[child + 1]) ? child : child + 1;
		}
		else {			// 절대값이 다른 경우에는 절대값 비교하여서 child를 바꿔주었다.
			child = (abs(heap[child] < abs(heap[child + 1]))) ? child : child + 1;
		}
	}
	while (abs(heap[child]) <= abs(heap[parent]) && child <= h_cnt) {		//insert와 마찬가지
		if (abs(heap[child]) == abs(heap[parent])&&heap[child]<heap[parent]) {
			swap(heap[child], heap[parent]);
		}
		else if (abs(heap[child]) == abs(heap[parent]) && heap[child] >= heap[parent]) break;
		else if (abs(heap[child]) < abs(heap[parent])) {
			swap(heap[child], heap[parent]);
		}
		parent = child;
		child = parent * 2;
		if (child + 1 <= h_cnt) {
			if (abs(heap[child]) == abs(heap[child + 1])) {
				child = (heap[child] < heap[child + 1]) ? child : child + 1;
			}
			else {
				child = (abs(heap[child] < abs(heap[child + 1]))) ? child : child + 1;
			}
		}
	}
	return result;
}

int main() {
	int n, num;
	scanf("%d", &n);
	for (int i = 0; i < n; i++){
		scanf("%d", &num);
		if (!num) {
			printf("%d\n", pop());
		}
		else {
			insert(num);
		}
	}
	return 0;
}

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

문제

문제

출처

ICPC

샘플은 맞았으나 어떤 부분때문에 런타임 에러가 났는지 궁금합니다.

kangsy763 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말