[백준 1181] 단어 정렬

 

C언어를 이용하여 코드를 작성하였다.

처음 코드에는 정렬을 할 때, O(n^2)인 정렬을 써서 시간 초과가 나서 검색해보니 

stdlib.h 파일에서 제공하는 qsort()라는 함수를 발견하여 qsort()함수를 이용하여 코드를 작성하였다.

 

#pragma warning(disable : 4996)
#include <stdio.h>
#include <stdlib.h>

typedef struct {
	int len;
	char str[51];
}words;

int compare(const void *a, const void *b) {
	words real_a = *(words*)a;
	words real_b = *(words*)b;
	int len_a = strlen(real_a.str);
	int len_b = strlen(real_b.str);
	if (len_a != len_b)
		return (len_a - len_b);
	return strcmp(real_a.str, real_b.str);
}

int main()
{
	words* word;
	words tmp;
	int flag = 0, real_n = 0;
	char strtmp[51] = {0};
	int n, i, j;
	scanf("%d", &n);
	word = (words*)malloc(sizeof(words) * n);
	for (i = 0;i < n;i++)
	{
		scanf("%s", strtmp);
		for (j = 0;j < i;j++) {
			if (strcmp(word[j].str, strtmp) == 0) {
				flag = 1;
				break;
			}
		}
		if (flag == 0) {
			strcpy(word[real_n].str, strtmp);
			word[real_n].len = strlen(strtmp);
			real_n++;
		}
		flag = 0;
	}
	qsort(word, real_n, sizeof(words), compare);
	for (i = 0;i < real_n;i++) printf("%s\n", word[i].str);
	free(word);
	return 0;
}

입력을 받으면서 이전에 입력 받았던 문자열이면 배열에 추가하지 않게 설정하였다.

qsort()를 사용하기 위해서는 어떤 방식으로 sort를 할 것인지에 대한 함수가 추가적으로 필요한데 여기서는 compare()를 추가적으로 사용하였다.

 

Compare()

int compare(const void *a, const void *b) {
	words real_a = *(words*)a;
	words real_b = *(words*)b;
	int len_a = strlen(real_a.str);
	int len_b = strlen(real_b.str);
	if (len_a != len_b)
		return (len_a - len_b);
	return strcmp(real_a.str, real_b.str);
}

compare 함수만 따로 살펴보자.

문제에서 요구한 것을 다시 생각해보면 a,b를 비교할 때, 길이가 다르면 (예를 들어 i, no) i가 우선순위가 더 높다. (길이가 짧으니까!!)

우선순위가 높은것이 더 작은 수라고 생각하면 된다.

(음.. 1과 2가 있을때, 우선순위가 1이 먼저지만 수는 1이 더 작은 느낌이랄까)

그래서 len_a - len_b가 음수가 나올것이고 그건 a가 우선순위가 더 높다는 것을 뜻한다. (반대의 경우, 즉 길이가 긴 것이 우선순위가 높을 때에는 len_a - len_b가 양수이기 때문에 우선순위가 낮으니까 (-1)을 곱해준 뒤 return 하면 된다.)

길이가 같을 때에는 사전 순으로 배열이기 때문에 strcmp()함수를 써서 return을 하게 해주었다.

strcmp()은 a,b를 비교해서 a가 작으면 음수를 리턴하기에 딱 알맞게 사용했다고 볼 수 있다.

 

배운점

1. qsort() 함수를 처음 봤다. 종종 사용해야겠다.

2. 퀵정렬과 힙정렬도 생각해봐야겠다....... 먼 미래에..