글 읽기 - C언어로 구현하는데 메모리 초과 오류가 납니다.

alsrl9 3년 전 0

queue를 이용한 위상 정렬로 문제를 해결하려고 했는데

제출하면 바로 메모리 초과로 오답 처리 되네요. ㅠ

메모리 사용을 줄이려고 동적 배열도 사용했는데 어디서 문제가 되는 건지 알 수 있을까요?

#include <stdio.h>
#include <stdlib.h>
#define MAX 32001

int N; // 학생 수
int M; // 키를 비교한 횟수

int *students[MAX];
int students_length[MAX];
int students_count[MAX];
int cnt_in_degree[MAX];

int queue[MAX];
int cnt_queue, idx_queue;

int check[MAX];
int cnt_check;

void push(int num){
	queue[cnt_queue++] = num;
}

int pop(){
	return queue[idx_queue++];
}

void addToQueue(){
	for (int i = 1; i <= N; i++)
		if (check[i] == 0 && cnt_in_degree[i] == 0)
			push(i);
}

void RemoveFromQueue(){
	int temp;
	while (cnt_queue > idx_queue){
		temp = pop();
		printf("%d ", temp);
		check[temp] = 1;
		cnt_check++;

		// remove line
		for (int i = 0; i < students_count[temp]; i++)
			cnt_in_degree[students[temp][i]]--;
	}
}

void addToList(int idx_student, int other_student){
	if (students_length[idx_student] == 0){
		students_length[idx_student] = 1;
		students[idx_student] = malloc(sizeof(int));
	}
	else if (students_length[idx_student] <= students_count[idx_student]){
		students_length[idx_student]++;
		students[idx_student] = realloc(students[idx_student], students_length[idx_student]);
	}

	students[idx_student][students_count[idx_student]] = other_student;
	students_count[idx_student]++;
	cnt_in_degree[other_student]++;
}

int main(){
	int input1, input2;
	scanf("%d %d", &N, &M);

	for (int i = 0; i < M; i++){
		scanf("%d %d", &input1, &input2);
		addToList(input1, input2);
	}

	while (cnt_check < N){
		addToQueue();
		RemoveFromQueue();
	}

	// free memories
	for (int i = 0; i <= N; i++)
		if (students_length[i] > 0)
			free(students[i]);
	return 0;    
}

djm03178 3년 전 1

realloc을 할 시에 길이에 sizeof(int)를 곱해서 할당해주어야 합니다.

alsrl9 3년 전 0

정말 감사합니다. 엉뚱한 곳에서 헤매고 있었는데 덕분에 해결됐어요.

이제 응답 시간을 줄일 수 있도록 고민해보겠습니다.

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

문제

문제

출처

ICPC

C언어로 구현하는데 메모리 초과 오류가 납니다.

alsrl9 3년 전 0

djm03178 3년 전 1

alsrl9 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말