글 읽기 - 이 문제 어떻게 접근해야할까요??

jumpingz 7년 전 0

STL 은 몰라서 못쓰겟고... 굳이 접근하자니 최대힙 최소힙을 이용해서 풀려고햇는데 자꾸 TLE 뜨네요...

힙을 쓰면 빠르긴하겟는데 최대 힙 및 최소 힙 사이에 동기화 시키는 과정이 오래걸려서 시간초과인거 같은데.. 어떻게 접근해야할까요???

아래는 일단 시간초과가 뜬 소스입니다...

#include <cstdio>

typedef struct _HEAP
{
	long long int * arr;
	int size;
}HEAP;

HEAP * MaxHeap = NULL, *MinHeap = NULL;

void InsertMin(long long int D);
long long int DeleteMin();
void InsertMax(long long int D);
long long int DeleteMax();

int main()
{
	long long int data, *A;
	int i, j, z = 0, N, T, flag = 0;
	char input[2];

	scanf("%d", &N);

	for (i = 0; i < N; i++)
	{
		scanf("%d", &T);

		MaxHeap = (HEAP*)malloc(sizeof(HEAP));
		MaxHeap->arr = (long long int*)malloc(sizeof(long long int) * 1000000);
		MaxHeap->size = 0;

		MinHeap = (HEAP*)malloc(sizeof(HEAP));
		MinHeap->arr = (long long int*)malloc(sizeof(long long int) * 1000000);
		MinHeap->size = 0;

		A = (long long int*)malloc(sizeof(long long int) * 1000000);

		for (j = 0; j < 1000000; j++)
		{
			MinHeap->arr[i] = 2147483648;
			MaxHeap->arr[i] = -2147483649;
		}
		
		for (j = 0; j < T; j++)
		{
			scanf("%s%lld", input, &data);

			if (flag == 0)
			{
				if (input[0] == 'I')
					InsertMax(data);
				else if (input[0] == 'D' && data == 1)
					DeleteMax();
				else if (input[0] == 'D' && data == -1)
				{
					while (MaxHeap->size != 0)
						InsertMin(DeleteMax());
					if (MinHeap->size != 0)
						DeleteMin();
					flag = 1;
				}
			}
			else
			{
				if (input[0] == 'I')
					InsertMin(data);
				else if (input[0] == 'D' && data == 1)
				{
					while (MinHeap->size != 0)
						InsertMax(DeleteMin());

					if (MaxHeap->size != 0)
						DeleteMax();
					flag = 0;
				}
				else if (input[0] == 'D' && data == -1)
					DeleteMin();
			}
		}

		if (flag == 0)
		{
			if (MaxHeap->size == 0)
				printf("EMPTY\n");
			else if (MaxHeap->size == 1)
				printf("%d %d\n", MaxHeap->arr[0], MaxHeap->arr[0]);
			else
			{
				printf("%d ", MaxHeap->arr[0]);

				while (MaxHeap->size != 1)
					DeleteMax();

				printf("%d\n", MaxHeap->arr[0]);
			}
		}
		else
		{
			if (MinHeap->size == 0)
				printf("EMPTY\n");
			else if (MinHeap->size == 1)
				printf("%d %d\n", MinHeap->arr[0], MinHeap->arr[0]);
			else
			{
				printf("%d ", MinHeap->arr[0]);

				while (MinHeap->size != 1)
					DeleteMin();

				printf("%d\n", MinHeap->arr[0]);
			}
		}
	}

	return 0;
}

void InsertMin(long long int D)
{
	int i = MinHeap->size++;

	while (i != 0 && MinHeap->arr[(i - 1) / 2] > D)
	{
		MinHeap->arr[i] = MinHeap->arr[(i - 1) / 2];
		i = (i - 1) / 2;
	}

	MinHeap->arr[i] = D;
}

void InsertMax(long long int D)
{
	int i = MaxHeap->size++;

	while (i != 0 && MaxHeap->arr[(i - 1) / 2] < D)
	{
		MaxHeap->arr[i] = MaxHeap->arr[(i - 1) / 2];
		i = (i - 1) / 2;
	}

	MaxHeap->arr[i] = D;
}

long long int DeleteMin()
{
	long long int parent, child, compare, ret;

	if (MinHeap->size == 0)	return 0;
	else if (MinHeap->size == 1)
	{
		ret = MinHeap->arr[0];
		MinHeap->arr[MinHeap->size - 1] = 2147483648;
		MinHeap->size--;
		return ret;
	}
	else
	{
		parent = 0;	child = 1;
		ret = MinHeap->arr[0];
		compare = MinHeap->arr[MinHeap->size - 1];	MinHeap->arr[MinHeap->size - 1] = 2147483648;
		MinHeap->size--;

		while (child <= MinHeap->size)
		{
			if (child < MinHeap->size && MinHeap->arr[child] > MinHeap->arr[child + 1])
				child++;

			if (compare <= MinHeap->arr[child])
				break;
			else
			{
				MinHeap->arr[parent] = MinHeap->arr[child];
				parent = child;
				child = child * 2 + 1;
			}
		}

		MinHeap->arr[parent] = compare;
		return ret;
	}
}

long long int DeleteMax()
{
	long long int parent, child, compare, ret;

	if (MaxHeap->size == 0)	return 0;
	else if (MaxHeap->size == 1)
	{
		ret = MaxHeap->arr[0];
		MaxHeap->arr[MaxHeap->size - 1] = -2147483649;
		MaxHeap->size--;
		return ret;
	}
	else
	{
		parent = 0;	child = 1;
		ret = MaxHeap->arr[0];
		compare = MaxHeap->arr[MaxHeap->size - 1];	MaxHeap->arr[MaxHeap->size - 1] = -2147483649;
		MaxHeap->size--;

		while (child <= MaxHeap->size)
		{
			if (child < MaxHeap->size && MaxHeap->arr[child] < MaxHeap->arr[child + 1])
				child++;

			if (compare >= MaxHeap->arr[child])
				break;
			else
			{
				MaxHeap->arr[parent] = MaxHeap->arr[child];
				parent = child;
				child = child * 2 + 1;
			}
		}

		MaxHeap->arr[parent] = compare;
		return ret;
	}
}

flflds0811 7년 전 1

STL 기본 틀만 아시면 쉽게 사용하실 수 있습니다. STL사용하시는 걸 추천드려요.

굳이 STL을 사용하지 않고 문제를 푸시겠다면, 동기화까지 고려하여

삽입,삭제 O(logN) 탐색 O(1)에 구현하시면 충분히 시간 안에 들어오는 것으로 알고 있습니다.

힙을 두개를 만들어 포인터로 연결하시는 방식으로 구현하시거나,

하나의 heap이 min_heap,max_heap 모두를 갖추고 있는 MIN_MAX_HEAP이라는 자료구조를 공부하신 후,

구현해보시는 것이 좋을 것 같습니다.

jumpingz 7년 전 0

min-max heap 자료구조 자세히 설명된 곳없을까요??? 삽입은 이해햇는데 삭제하는 방식이 구글링해서 찾은 자료로는 도무지 이해가 안가서리....

flflds0811 7년 전 0

아쉽지만 저는 학교 강의자료를 통해 공부한거라.. 따로 설명이 잘 되있는 곳은 모르겠네요..ㅜㅜ

jumpingz 7년 전 0

그러면 죄송하지만 요 코드좀 봐주실수잇나요?? min-max 공부하고 짯는데 계속 시간초과가 떠서 어디가 문제인지모르겟어요..

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)

#define MIN 0
#define MAX 1
#define SUCCESS 1
#define FAIL -1


typedef struct _HEAP
{
	long long int * arr;
	int size;
}HEAP;

HEAP * Heap = NULL;

void Insert_Max(int parent, int data);
void Insert_Min(int parent, int data);
void Insert(int data);
int level(int size);
long long int Delete_Max();
long long int Delete_Min();

int main()
{
	char str[2];
	int i, j, N, K, data;

	scanf("%d", &N);

	for (i = 0; i < N; i++)
	{
		scanf("%d", &K);

		Heap = (HEAP*)malloc(sizeof(HEAP));
		Heap->arr = (long long int*)malloc(sizeof(long long int) * K);
		Heap->size = 0;

		for (j = 0; j < K; j++)
		{
			scanf("%s%d", str, &data);

			if (str[0] == 'I')
				Insert(data);
			else if (str[0] == 'D' && data == 1)
				Delete_Max();
			else if (str[0] == 'D' && data == -1)
				Delete_Min();
		}

		if (Heap->size == 0)
			printf("EMPTY\n");
		else if (Heap->size == 1)
			printf("%lld %lld\n", Heap->arr[1], Heap->arr[1]);
		else if(Heap->size == 2)
			printf("%lld %lld\n", Heap->arr[2], Heap->arr[1]);
		else
		{
			if (Heap->arr[2] > Heap->arr[3])
				printf("%lld ", Heap->arr[2]);
			else
				printf("%lld ", Heap->arr[3]);

			printf("%lld\n", Heap->arr[1]);
		}
		free(Heap->arr);
		free(Heap);
	}
	return 0;
}

int level(int size)
{
	int count = 0;

	while (size != 0)
	{
		size /= 2;
		count++;
	}

	if (count % 2 != 0)
		return MIN;
	else
		return MAX;
}

void Insert(int data)
{
	int parent;

	Heap->size++;
	parent = Heap->size / 2;
	
	if (parent == 0)
		Heap->arr[1] = data;
	else
	{
		if (level(Heap->size) == MIN)
		{
			if (data > Heap->arr[parent])
			{
				Heap->arr[Heap->size] = Heap->arr[parent];
				Insert_Max(parent, data);
			}
			else
				Insert_Min(Heap->size, data);
		}
		else
		{
			if (data < Heap->arr[parent])
			{
				Heap->arr[Heap->size] = Heap->arr[parent];
				Insert_Min(parent, data);
			}
			else
				Insert_Max(Heap->size, data);
		}
	}
}

void Insert_Min(int parent , int data)
{
	int grandparent = parent / 4;

	while (grandparent != 0)
	{
		if (data < Heap->arr[grandparent])
		{
			Heap->arr[parent] = Heap->arr[grandparent];
			parent = grandparent;
			grandparent /= 4;
		}
		else
			break;
	}

	Heap->arr[parent] = data;
}

void Insert_Max(int parent, int data)
{
	int grandparent = parent / 4;

	while (grandparent != 0)
	{
		if (data > Heap->arr[grandparent])
		{
			Heap->arr[parent] = Heap->arr[grandparent];
			parent = grandparent;
			grandparent /= 4;
		}
		else
			break;
	}

	Heap->arr[parent] = data;
}

long long int Delete_Min()
{
	int i, temp, index;
	long long int min, imsi, returnValue;
	if (Heap->size == 0)
		return FAIL;

	returnValue = Heap->arr[1];
	Heap->arr[1] = Heap->arr[Heap->size];
	Heap->arr[Heap->size] = -2147438648;
	Heap->size--;

	// 기존에 데이터가 한개 남앗던 경우
	if (Heap->size == 0)
		return returnValue;

	temp = 1;

	while (1)
	{
		min = 2147483648; index = -1;

		if (temp * 2 > Heap->size) // 자식노드가 존재하지 않는 경우
			break;
		else
		{
			for (i = 0; i < 2; i++)
			{
				if (temp * 2 + i > Heap->size)
					break;
				
				if (Heap->arr[temp * 2 + i] < Heap->arr[temp])
				{
					if (min > Heap->arr[temp * 4 + i])
					{
						min = Heap->arr[temp * 2 + i];
						index = temp * 2 + i;
					}
				}
			}

			if (index != -1)
			{
				imsi = Heap->arr[temp];
				Heap->arr[temp] = min;
				Heap->arr[index] = imsi;
			}
		}

		if (temp * 4 > Heap->size) // 자손노드가 존재하지 않는 경우
			break;
		else
		{
			for (i = 0; i < 4; i++)
			{
				if (temp * 4 + i > Heap->size)
					break;
				else
				{
					if (Heap->arr[temp * 4 + i] < Heap->arr[temp])
					{
						if (min > Heap->arr[temp * 4 + i])
						{
							min = Heap->arr[temp * 4 + i];
							index = temp * 4 + i;
						}
					}
				}
			}

			if (index != -1)
			{
				imsi = Heap->arr[temp];
				Heap->arr[temp] = min;
				Heap->arr[index] = imsi;
				temp = index;
			}
		}
	}
	
	return returnValue;
}

long long int Delete_Max()
{
	// size 가 1 인 경우 처리해야함
	int i, temp, index;
	long long int max, returnValue, imsi;
	if (Heap->size == 0)
		return FAIL;

	if (Heap->size == 1)
	{
		returnValue = Heap->arr[1];
		Heap->arr[1] = -2147438648;
		Heap->size--;
		return returnValue;
	}

	if (Heap->arr[2] > Heap->arr[3])
	{
		returnValue = Heap->arr[2];
		Heap->arr[2] = Heap->arr[Heap->size];
		temp = 2;
	}
	else
	{
		returnValue = Heap->arr[3];
		Heap->arr[3] = Heap->arr[Heap->size];
		temp = 3;
	}

	Heap->arr[Heap->size] = -1;
	Heap->size--;

	if (Heap->size == 0)
		return returnValue;

	while (1)
	{
		max = -2147438648; index = -1;

		if (temp * 2 > Heap->size) // 자식노드가 존재하지 않는 경우
			break;
		else
		{
			for (i = 0; i < 2; i++)
			{
				if (temp * 2 + i > Heap->size)
					break;

				if (Heap->arr[temp * 2 + i] > Heap->arr[temp])
				{
					if (max < Heap->arr[temp * 2 + i])
					{
						max = Heap->arr[temp * 2 + i];
						index = temp * 2 + i;
					}
				}
			}

			if (index != -1)
			{
				imsi = Heap->arr[temp];
				Heap->arr[temp] = max;
				Heap->arr[index] = imsi;
			}
		}

		if (temp * 4 > Heap->size) // 자손노드가 존재하지 않는 경우
			break;
		else
		{
			for (i = 0; i < 4; i++)
			{
				if (temp * 4 + i > Heap->size)
					break;
				else
				{
					if (Heap->arr[temp * 4 + i] > Heap->arr[temp])
					{
						if (max < Heap->arr[temp * 2 + i])
						{
							max = Heap->arr[temp * 4 + i];
							index = temp * 4 + i;
						}
					}
				}
			}

			if (index != -1)
			{
				imsi = Heap->arr[temp];
				Heap->arr[temp] = max;
				Heap->arr[index] = imsi;
				temp = index;
			}
		}
	}

	return returnValue;



}

flflds0811 7년 전 0

쭉 보았을 때, 복잡도상 문제는 아닌것 같습니다.

몇 %까지 가시다 시간초과가 나시는지..?

최적화 문제일 것같습니다.

분기문이 많은 편이라 제한시간 안에 들어오지 못하는 것 아닐까요??

ㅜㅜ

jumpingz 7년 전 0

그냥 시작부터 시간초과나더라구요 ㅋㅋㅋ 부끄럽지만 1%.. ㅠ 아 이틀넘게 자료 찾으면서 공부햇는데.. 허탈하네요.. 분기문을 좀 어떻게 줄여보면 되려는지요...?

flflds0811 7년 전 0

글쎄요.... 확신은 못 하겠네요;; 저는 포인터로 연결하는 방식으로 짜둔걸 제출했을 때

3100으로 통과한거라 시간복잡도가 만족해도 앞의 상수가 커지면 시간초과가 나는 것 같은데;;

어느정도로 맞춰야하는지는 저도 잘 모르겠네요...ㅜ

jumpingz 7년 전 0

아... 동일한 값이 여러개 입력되면 삭제 시 무한루프가 발생하는걸 찾앗습니다... 일단 요걸 해결해봐야할 듯하네요 ㅎㅎㅎ

감사합니다.

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

문제

문제

출처

ICPC

이 문제 어떻게 접근해야할까요??

jumpingz 7년 전 0

flflds0811 7년 전 1

jumpingz 7년 전 0

flflds0811 7년 전 0

jumpingz 7년 전 0

flflds0811 7년 전 0

jumpingz 7년 전 0

flflds0811 7년 전 0

jumpingz 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말