글 읽기 - malloc 및 mergesort 질문입니다

eden0821 1년 전 0

mergesort를 이용해서 정렬을 시도 했고

malloc을 이용해보았는데

어디가 잘못된건지 알 수 있을까요..?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _string {
	char str[51];
	int len;
}string;
string sorted[20001];
void merge(string* data, int start, int mid, int end) {
	int i = start;
	int j = mid + 1;
	int k = start;

	while (i <= mid && j <= end) {
		if (data[i].len < data[j].len) {
			sorted[k++] = data[i++];
		}
		else if(data[i].len>data[j].len) {
			sorted[k++] = data[j++];
		}
		else {
			if (strcmp(data[i].len, data[j].len) < 0)
				sorted[k++] = data[i++];
			else
				sorted[k++] = data[j++];
		}
	}
	if (i > mid) {
		for (int t = j; t <= end; t++) {
			sorted[k] = data[t];
			k++;
		}
	}
	else {
		for (int t = i; t <= mid; t++) {
			data[t] = sorted[t];
			k++;
		}
	}
	for (int t = start; t <= end; t++) {
		data[t] = sorted[t];
	}
}
void mergeSort(string* data, int start, int end) {
	if (start < end) {
		int mid = (start + end) / 2;
		mergeSort(data, start, mid);
		mergeSort(data, mid + 1, end);
		merge(data, start, mid, end);
	}
}
int main(void) {
	int N;
	scanf("%d", &N);
	string* arr= (string*)malloc(sizeof(string)*N);

	for (int i = 0; i < N; i++) {
		scanf("%s", arr[i].str);
		arr[i].len = strlen(arr[i].str);
	}
	
	mergeSort(arr, 0, N-1);
	printf("%s\n", arr[0].str);
	for (int i = 1; i < N; i++) {
		if (strcmp(arr[i - 1].str, arr[i].str) != 0)
			printf("%s\n", arr[i].str);
	}
	free(arr);
	return 0;
}

zenith82114 1년 전 1

22번 줄에서 strcmp에 int형인 len을 넘기는 부분이 문제의 소지가 있어 보이고

merge 함수에서 string 구조체 사이에 단순히 =를 써버리면
실제 str 안의 값이 아니라 주소가 복사될 거라서
strcpy 등으로 깊은 복사를 해줘야 할 겁니다.

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

문제

문제

출처

ICPC

malloc 및 mergesort 질문입니다

eden0821 1년 전 0

zenith82114 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말