글 읽기 - c언어 mergesort 구현해봤는데...

douglas0421 2년 전 0

4 2
3 sunyoung
2 junkyu
2 dohyun    입력값들
1 minjun
3 kihyun
2 damin
4 hyunsu
0 0

7 4 3 
2 junkyu    앞 class가 짝수일때 arr에 저장한 값들 출력
2 dohyun
2 damin
4 hyunsu

3 sunyoung
1 minjun    앞 class가 홀수일때 arr1에 저장한 값들 출력
3 kihyun

1 minjun
3 sunyoung    arr1 mergesort로 내림차순 정렬
2 damin

2 damin
2 junkyu
2 damin        arr mergesort로 내림차순 정렬

할려했지만 arr 과 arr1에는 잘 저장되는 거같지만 meregesort가 잘 작동안합니다.

meregesort를 class가 빠른순서대로 class가 같으면 이름 길이순으로 이름 길이도 같으면 사전순으로 정렬하려합니다. 조언 부탁드립니다. ㅠㅠ 1주일째 고민중입니다.

#include <stdio.h>       
#include <stdlib.h>
#include <string.h>

typedef struct {
	int class;
	char name[15];
}Class;

Class buff[1001];

void merge(Class *c, int first, int mid, int last)
{
	int i = first;
	int j = mid + 1;
	int k = first;
	while(i <= mid && j <= last)    
	{
		if(c[i].class < c[j].class) //우선 클래스 순으로 정렬
			buff[k++] = c[i++];
		else if(c[i].class > c[j].class)
			buff[k++] = c[j++];
		else
		{        //클래스가 같으면 이름 길이순으로 정렬
			if(strlen(c[i].name) > strlen(c[j].name))
				buff[k++] = c[j++];
			else if(strlen(c[i].name) < strlen(c[j].name))
				buff[k++] = c[i++];
			else
			{        //클래스가 같고 이름길이도 같으면 사전순으로 정렬
				if(strcmp(c[i].name, c[j].name) > 0)
					buff[k++] = c[j++];
				else
					buff[k++] = c[i++];
			}
		}
		if(i > mid)
		{
			while(j <= last)
				buff[k++] = c[j++];
		}
		else if(j > last)
		{
			while(i <= mid)
				buff[k++] = c[i++];
		}
		for(k = first; k <= last; k++)
			c[k] = buff[k];
	}
}

void mergesort(Class *bb, int first, int last)
{
	int mid;
	if(first < last)
	{
		mid = (first + last) / 2;
		mergesort(bb, first, mid);
		mergesort(bb, mid + 1, last);
		merge(bb, first, mid ,last);
	}
}

int main()
{
	Class c[500];
	Class arr[500];
	Class arr1[500];
	int num[10] = {0,};
	
	int n, m, cnt = 0;
	scanf("%d %d",&n,&m);
	int cnt1 = 0, cnt2 = 0;
	while(1)
	{
		scanf("%d %s",&c[cnt].class, c[cnt].name);
		if(c[cnt].class == 0 && strcmp(c[cnt].name, "0") == 0)
			break;
		cnt++;
	}

	for(int i = 0; i < cnt; i++)
	{
		if(c[i].class % 2 == 0)
		{
			arr[cnt1].class = c[i].class;
			strcpy(arr[cnt1].name, c[i].name);
			cnt1++;
		}
		else
		{
			arr1[cnt2].class = c[i].class;
			strcpy(arr1[cnt2].name, c[i].name);
			cnt2++;
		}                                 //cnt = c에 저장된 값 갯수     
	}                                     //cnt2 = arr1에 저장된 값 갯수
	printf("%d %d %d\n",cnt, cnt1, cnt2); //cnt1 = arr에 저장된 값 갯수
	for(int i = 0; i < cnt1; i++) 
		printf("%d %s\n", arr[i].class, arr[i].name);
	putchar('\n');
	for(int i = 0; i < cnt2; i++)
		printf("%d %s\n", arr1[i].class, arr1[i].name);
	putchar('\n');
	mergesort(arr, 0, cnt1-1);        
	mergesort(arr1, 0, cnt2-1);
	
	for(int i = 0; i < 3; i++)
		printf("%d %s\n", arr1[i].class, arr1[i].name);
	putchar('\n');
	for(int i = 0; i < 3; i++)
		printf("%d %s\n", arr[i].class, arr[i].name);
	return 0;
}

hoxymola 2년 전 1

37~48번 줄을 while문 밖으로 빼셔야될거같아요~~

douglas0421 2년 전 1

진짜 감사합니다! ㅠㅠ

douglas0421 2년 전 0

혹시 이 코드 시간복잡도 줄일 수 있는 방법 알고 계십니까

douglas0421 2년 전 0

덕분에 답은 알맞게 나올수잇었습니다. 감사합니다!

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

문제

문제

출처

ICPC

c언어 mergesort 구현해봤는데...

douglas0421 2년 전 0

hoxymola 2년 전 1

douglas0421 2년 전 1

douglas0421 2년 전 0

douglas0421 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말