글 읽기 - 11286 c언어 질문!

ehdgud583205 2년 전 0

제출하면 틀렸다고 뜨는데 어느 부분이 문제일까요?

아마 insert 부분이 문제일 거 같긴 한데

막상 코드를 보면 어떤 내용이 잘못되었는지 감이 안 오네요..

도와 주세요 고수 형님들

#include <stdio.h>
#include <string.h>
#define MAX_N 100001

int heap[MAX_N];
int size=0;

void swap(int *a, int *b) 
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

int GetIdx(int idx)
{
	if((idx*2) > size)    // 자식 노드가 없다면
		return idx;
		 
	else if((idx*2) == size)    // 왼쪽 자식 노드가 마지막 노드라면
		return (idx*2);

	else   // 왼쪽 자식 노드와 오른쪽 자식 노드의 우선순위를 비교
	{
		int cha_right=heap[(idx*2)+1];
		int cha_left=heap[(idx*2)];
		
		if(heap[(idx*2)+1] < 0)
			cha_right=heap[(idx*2)+1] * (-1);
			
		if(heap[(idx*2)] < 0)
			cha_left=heap[(idx*2)] * (-1);
			
		if(cha_right < cha_left)
			return (idx*2)+1;
		else if(cha_left < cha_right)
			return (idx*2);
		else
		{
			if(heap[idx*2] < heap[(idx*2)+1])
				return idx*2;
			else
				return (idx*2)+1;
		}
	}
}

void insert(int data)
{
	int idx= ++size;
	
	int cha_data=data;
	int cha_parent;
	if(idx!=1)
		cha_parent=heap[idx/2];
	else
		cha_parent=0;
		
	if(data<0)
		cha_data=data*(-1);
	
	if(heap[idx/2]<0)
		cha_parent=heap[idx/2]*(-1);

	while((idx!=1) && (cha_data<cha_parent))
	{
		heap[idx]=heap[idx/2];
		idx=idx/2;
		
		if(heap[idx/2]<0)
			cha_parent=heap[idx/2]*(-1);
		else if(heap[idx/2]>0)
			cha_parent=heap[idx/2];
	}
	
	if(cha_data==cha_parent)
	{
		while((idx!=1) && (data<heap[idx/2]))
		{
			heap[idx]=heap[idx/2];
			idx=idx/2;
		}
	}
	
	heap[idx]=data;
}

int deleteheap()
{
	if (size==0)
		return 0;
		
	int value=heap[1];
	
	heap[1]=heap[size--]; // size 하나 줄어야함. 
	int parent=1;
	int child;
	
	while(1)
	{
		child=GetIdx(parent);
		
		int cha_child=heap[child];
		int cha_parent=heap[parent];
		
		if(heap[parent] < 0)
			cha_parent=heap[parent] * (-1);
		
		if(heap[child] < 0)
			cha_child=heap[child] * (-1);
		
		if(cha_parent<cha_child)
			break;
		else if(cha_parent == cha_child)
		{
			if(heap[parent] <= heap[child])
				break;			
		}
		
		swap(&heap[parent],&heap[child]);
		parent=child;
	}
	
	return value;
}

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

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

문제

문제

출처

ICPC

11286 c언어 질문!

ehdgud583205 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말