[C] 백준 | 1181번 코드 - 단어 정렬

>문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

> 핵심

O(nlogn) 정렬방법을 이용하자(합병정렬, 퀵정렬, 힙정렬)

>풀이과정

정렬. 대학교에 처음 들어와서 배우는 버블정렬부터 시작해

알고리즘 시간에 배우는 삽입, 선택정렬, 힙정렬, 합병정렬, 퀵정렬 등등등,, 종류가 참 다양하다.

 

예전에 수업자료 ppt에 있던거 캡쳐해서 가져왔다. 인터넷에 올려도 되겠지?

 

정렬도 안해본지 오래되니 다 까먹고 예전에 써뒀던 코드를 보니 너무 낯설었다.

감이 녹슬지 않게 꾸준히 알고리즘을 익혀둬야겠다는 생각이 들었다.

 

합병정렬은 그나마 뭔가 직관적이고 할만한데

정석적인 퀵정렬을 직접 만드려니 도저히 모르겠어서 포기했다.

단순 길이순 정렬은 하겠는데 사전순 정렬까지 끼워서 같이 생각하려니 나의 돌머리로는 도저히 구현이 불가능했다.

 

다른사람들 코드 보니 그냥 라이브러리에 있는 qsort 함수를 쓰는 것 같았다.. 나도 그냥 그거 써야겠다.

퀵정렬을 굳이 수업시간에 배운대로 정석적으로 쓸 필요는 없으니.. 합병정렬이나 잘 해야지.

 

 

#이 문제를 통해 배운것

1. 합병정렬, 퀵정렬 방법과 시간복잡도

- 퀵정렬의 경우 피봇선택에 따라 시간복잡도가 O(nlogn)이 될수도, 최악의 경우에는 O(n^2)이 될 수도 있다.

- 그래서 피봇을 배열의 제일 왼쪽, 오른쪽 같은데로 고정해서 잡으면 제 성능을 못낼 수도 있다. (정렬된 배열일 경우)

 

2.. strcmp 함수!

- strcmp(문자열 1, 문자열 2) < 0 == 문자열 1 < 문자열 2 처럼 생각하면 이해가 쉽다.

- 맨 앞부터 차례차례 비교한다. abc < b,  aaa < abc,  aaa < aaaaa 와 같다.

 

3. qsort 함수 사용방법.

void qsort (void *base, size_t nel, size_t width, int (*compare)(const void *, const void *)

base : 정렬하고자 하는 배열 --> text

nel : 배열 요소의 총 갯수 --> n개

width : 배열 한칸의 크기 --> sizeof(text[0])

compare : 비교함수 (직접 만들어야함)

int compare(const void* first, const void* second)
{
	Word *a = (Word*)first;
	Word *b = (Word*)second;

	if (a->len < b->len)
		return -1;
	else if (a->len > b->len)
		return 1;
	else if (a->len == b->len)
	{
		if (strcmp(a->str, b->str) < 0)
			return -1;
		else
			return 1;
	}
	return 0;
}

compare 함수는 내가 짠 조건에 따라 -1, 0, 1 을 리턴하면 된다.

 

>근데 왜 어려운 const void*가 등장하지? 그냥 char 쓰면 안될까?

- qsort 함수는 int 뿐만 아니라 여러 자료형을 비교하는데 범용적으로 사용되기 때문에 그렇게 쓰면 안된다.(?)

- const 를 붙인 이유는 포인터의 avoid accidental changes 어쩌고.. 를 방지하기 위해서 라고 한다. 

포인터가 꼬였을때 오류를 방지하기 위한 느낌인가 싶다. 하여튼 포인터가 C 만악의 근원이다

그래서 void로 받고 강제 형변환을 해서 서로 비교한다.

 

>코드

1. 합병정렬

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

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

void merge(Word list[], int left, int mid, int right)
{
	Word* tmp_list;
	int i, j, k;

	tmp_list = (Word*)calloc(right + 1, sizeof(Word)); // 임시 배열 할당

	i = k = left;
	j = mid + 1;

	while (i <= mid && j <= right)
	{
		if (list[i].len < list[j].len)
			tmp_list[k++] = list[i++];
		else if (list[j].len < list[i].len)
			tmp_list[k++] = list[j++];
		else /* 길이가 같은 경우 사전순 정렬 */
		{
			if (strcmp(list[i].str, list[j].str) < 0)
				tmp_list[k++] = list[i++];
			else
				tmp_list[k++] = list[j++];
		}

	}
	while (i <= mid)
	{
		tmp_list[k++] = list[i++];
	}
	while (j <= right)
	{
		tmp_list[k++] = list[j++];
	}

	for (k = left; k <= right; k++)
	{
		list[k] = tmp_list[k];
	}

	free(tmp_list);
}

void merge_sort(Word list[], int left, int right)
{
	if (left < right)
	{
		int mid = (left + right) / 2;
		merge_sort(list, left, mid);
		merge_sort(list, mid + 1, right);
		merge(list, left, mid, right);
	}
}

int main()
{
	int i, j, n;
	Word* text;

	scanf("%d", &n);

	text = (Word*)calloc(n + 1, sizeof(Word));

	for (i = 0; i < n; i++)
	{
		scanf(" %s", text[i].str);
		text[i].len = strlen(text[i].str);

		/*중복 제거*/
		for (j = 0; j < i; j++)
		{
			if (strcmp(text[i].str, text[j].str) == 0) 
			{
				i -= 1;
				n -= 1;
				break;
			}
		}
	}

	merge_sort(text, 0, n - 1);

	for (i = 0; i < n; i++)
	{
		printf("%s\n", text[i].str);
	}

	return 0;
}

2. 퀵정렬

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

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

int compare(const void* first, const void* second)
{
	Word *a = (Word*)first;
	Word *b = (Word*)second;

	if (a->len < b->len)
		return -1;
	else if (a->len > b->len)
		return 1;
	else if (a->len == b->len)
	{
		if (strcmp(a->str, b->str) < 0)
			return -1;
		else
			return 1;
	}
	return 0;
}

int main()
{
	int i, j, n;
	Word* text;

	scanf("%d", &n);

	text = (Word*)calloc(n + 1, sizeof(Word));

	for (i = 0; i < n; i++)
	{
		scanf(" %s", text[i].str);
		text[i].len = strlen(text[i].str);

		/*중복 제거*/
		for (j = 0; j < i; j++)
		{
			if (strcmp(text[i].str, text[j].str) == 0) 
			{
				i -= 1;
				n -= 1;
				break;
			}
		}
	}

	qsort(text, n, sizeof(text[0]), compare);

	for (i = 0; i < n; i++)
	{
		printf("%s\n", text[i].str);
	}

	return 0;
}