글 읽기 - C언어 연결리스트 시간초과가 나네요ㅠㅠ

fruit1445 3년 전 0

자료구조 배운지 얼마 안 됐습니다.

배열은 메모리 초과가 떠서 연결리스트로 바꿨더니 시간 초과가 발생하네요.

연결리스트 말고 다른 방법으로 풀어야 할까요..?

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef struct {
	int data;
	struct Node *next;
}Node;

void getNode(int data, Node* header);
void freeNode(Node *header);
void show(Node* header);

int main(void)
{
	Node* header = (Node*)malloc(sizeof(Node));
	header->next = NULL;
	int n, data;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &data);
		getNode(data, header);
	}
	show(header);
    freeNode(header);
    free(header);
	return 0;
}

void getNode(int data, Node *header)
{
	Node *node = (Node*)malloc(sizeof(Node));
	node->data = data;
	Node* cur = header->next;
	Node* pre = header;
	while (cur != NULL && cur->data < data)
	{
		pre = cur;
		cur = cur->next;
	}
	node->next = pre->next;
	pre->next = node;
}

void freeNode(Node *header)
{
	Node* cur = header->next;
	while (cur != NULL)
	{
		Node* next = cur->next;
		free(cur);
		cur = next;
	}
}

void show(Node* header)
{
	Node* cur = header->next;
	while (cur != NULL)
	{
		printf("%d\n", cur->data);
		cur = cur->next;
	}
}

이 문제는 N이 매우 크고 메모리가 8MB밖에 안 되기 때문에 값을 모두 저장하지 못합니다. 이 문제를 풀 때는 각 값들이 매우 작다는 것에 유의해야 합니다. 각 값들이 10000 이하이므로, cnt 배열을 만들고 각 수들의 개수를 세서 O(n)에 정렬할 수 있습니다. STL 정렬 함수나 직접 구현한 O(n log n) 정도의 정렬 함수로는 이 문제를 풀지 못합니다.

sonjaewon 3년 전 1

카운팅 정렬 에 대해 알아보세요.

fruit1445 3년 전 0

카운팅 정렬에 대해서 처음 알았습니다!

바로 풀리네요

감사합니다!

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

문제

문제

출처

ICPC

C언어 연결리스트 시간초과가 나네요ㅠㅠ

fruit1445 3년 전 0

benedict0724 3년 전 1

sonjaewon 3년 전 1

fruit1445 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말