글 읽기 - 도저히 반례를 못찾겠습니다. 왜 틀린걸까요?ㅠㅠ

ysysysy3333 1년 전 0

머지소트에 함수를 하나 더 넣어서 풀어보았는데 완벽히 사전순서로 정렬이 안된 부분들이 있기에 머지소트를 한번 더 실시해서 출력하니까 완벽히 출력이 되는데 무슨 반례가 있는걸까요?

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

int n;

typedef struct word {
	char s[51];//최대 문자열의 길이 50 + null
	int leng;//문자열의 길이 저장
}word;



char compare(char si[], char sj[]) {
	int k = 0;
	while (1) {
		if (si[k] == '\0' || sj[k] == '\0'){//NULL값이 나올때까지 반복
			sj[0] = '\0';			//같은 단어일경우만 여기까지 반복됨
			return 'a';	//같은 단어일 경우 둘 중하나에 0번째 인덱스에
		}               //NULL값을 넣어 구분하여 추후 출력때 이용

		if (si[k] > sj[k]) {
			return 'j'; //j가 사전순으로 앞순서일 경우
		}
		else if (si[k] < sj[k]) {
			return 'i'; //i가 앞순서일 경우
		}
		else {
			k++; 
		}
	}
}
void merge(word words[], int a, int mid, int b) {
	int i = a, j = mid + 1, k = a;
	word* tmp = (word*)malloc(sizeof(word) * n);

	while (i <= mid && j <= b) {
		if (words[i].leng == words[j].leng) {//길이가 같은 경우 
			if (compare(words[i].s, words[j].s) == 'i') {
				tmp[k] = words[i];
				i++;
			}
			else if (compare(words[i].s, words[j].s) == 'j') {
				tmp[k] = words[j];
				j++;
			}else{
				tmp[k] = words[i];
				i++;
			}
		}
		else if (words[i].leng < words[j].leng) {//길이가 다른 경우 
			tmp[k] = words[i];
			i++;
		}
		else {
			tmp[k] = words[j];
			j++;
		}
		k++;
	}
	if (i > mid) {
		for (int t = j; t <= b; t++) {
			tmp[k] = words[t];
			k++;
		}
	}
	else {
		for (int t = i; t <= mid; t++) {
			tmp[k] = words[t];
			k++;
		}
	}
	for (int t = a; t <= b; t++) {
		words[t] = tmp[t];
	}
	free(tmp);
}
void mergeSort(word words[], int a, int b) {
	if (a < b) {
		int mid = (a + b) / 2;
		mergeSort(words, a, mid);
		mergeSort(words, mid + 1, b);
		merge(words, a, mid, b);
	}
}
int main(void)
{
	
	scanf("%d", &n);
	
	word* words = (word*)malloc(sizeof(word) * n);//구조체 할당

	for (int i = 0; i < n; i++) {
		scanf("%s", words[i].s); //단어입력
		words[i].leng = strlen(words[i].s);//단어별 길이 저장
	}
	mergeSort(words, 0, n - 1);//병합정렬
							//병합정렬 중 사전순서가 안되는 부분들이 발견됨
	mergeSort(words, 0, n - 1);//소트 후에 사전순서 안되는 부분들이 있어 재정렬
							 //성공적으로  정렬 완료
	for (int i = 0; i < n; i++) {
		
		if (words[i].s[0] == '\0') {//compar함수에서 겹친 문자열에 할당한 것들 
			continue;				//제외 후 출력
		}
		printf("%s\n", words[i].s);
	}

	free(words);
	return 0;
}

dldyddlwl 1년 전 1

4
a
b
c
a

ysysysy3333 1년 전 0

덕분에 맞혔습니다 ㅎ

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

문제

문제

출처

ICPC

도저히 반례를 못찾겠습니다. 왜 틀린걸까요?ㅠㅠ

ysysysy3333 1년 전 0

dldyddlwl 1년 전 1

ysysysy3333 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말