글 읽기 - 97퍼센트에서 틀린 이유를 모르겠습니다.

qktlf789456 3년 전 0

코드가 좀 복잡할 수 있으나,

제일 큰 길이의 수가 예를들어 1234 라면,

1234의 4자리 이하의 모든 수를 0으로 패딩시킨 후 해당 데이터를 우선순위큐를 사용하여 풀었습니다.

90퍼 이상에서 틀렸는데 이유를 모르겠네요.

값이 모두 0인경우 처리도 하였습니다..ㅠ

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define EMPTY -123456


/*

5
3 30 34 5 9


*/

struct node
{
	int compare_data;
	char *original_data;
	int original_size;
};


int size;


char** arr;

int max_size = 0;



struct node heap[1001];
int heap_size = 0;

void insert_heap(int compare_data, char* original_data, int original_size)
{
	heap_size++;

	int current = heap_size - 1;
	int parent = (current - 1) / 2;

	while (  (current != 0 && compare_data > heap[parent].compare_data)  || (current != 0 && compare_data == heap[parent].compare_data  && original_size < heap[parent].original_size)         )
	{
		heap[current] = heap[parent];

		current = parent;
		parent = (current - 1) / 2;
	}

	heap[current].compare_data = compare_data;
	heap[current].original_data = original_data;
	heap[current].original_size = original_size;
}


struct node delete_prior_heap()
{
	struct node return_node = { EMPTY, EMPTY, EMPTY };
	if (heap_size <= 0)
		return return_node;



	return_node.compare_data = heap[0].compare_data;
	return_node.original_data = heap[0].original_data;
	return_node.original_size = heap[0].original_size;
	


	int key = heap[--heap_size].compare_data;
	char* key_original = heap[heap_size].original_data;
	int key_original_size = heap[heap_size].original_size;

	int current = 0;
	int child = 1;

	while (child < heap_size)
	{
		if (  (child + 1 < heap_size && heap[child].compare_data < heap[child + 1].compare_data )    ||  (child+1 && heap[child].compare_data == heap[child + 1].compare_data  && heap[child].original_size > heap[child + 1].original_size)            )
			child++;


		if (key > heap[child].compare_data ||  (key == heap[child].compare_data && key_original_size < heap[child].original_size)  )
			break;

		heap[current] = heap[child];


		current = child;
		child = current * 2 + 1;
	}
	

	heap[current].compare_data = key;
	heap[current].original_data = key_original;
	heap[current].original_size = key_original_size;

	return return_node;
}




void padding_insert(char* data)
{
	int new_data = 0;

	int chk = 0;

	int original_size = 0;
	for (int i = 0; i < max_size; i++)
	{
		new_data *= 10;
		

		if (data[i] == NULL)
		{
			chk = 1;
			original_size = i;
		}

		if (chk == 0)
		{
			new_data += data[i] - '0';
		}
		else
		{
			new_data += 0;
		}
	}
	if (original_size == 0)
		original_size = max_size;



	insert_heap(new_data, data, original_size);


}

int main()
{
	scanf("%d", &size);

	arr = (char**)malloc(sizeof(char*) * size);

	for (int i = 0; i < size; i++)
	{
		arr[i] = (char*)malloc(11);
		scanf("%s", arr[i]);

		int j = 0;
		for (; arr[i][j] != NULL; j++);

		if (max_size < j)
			max_size = j;
	}

	for (int i = 0; i < size; i++)
	{
		padding_insert(arr[i]);
	}



	int chk2 = 0;
	for (int i = 0; i < size; i++)
	{
		struct node next_node = delete_prior_heap();

		if (next_node.compare_data != 0)
			chk2 = 1;

		if (chk2)
		{
			int current = 0;
			while (next_node.original_data[current] != NULL)
			{
				printf("%c", next_node.original_data[current]);
				current++;
			}
		}
	}

	if (chk2 == 0)
		printf("0");







	return 0;
}

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

문제

문제

출처

ICPC

97퍼센트에서 틀린 이유를 모르겠습니다.

qktlf789456 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말