[C] 백준 1181번 : 단어 정렬

https://www.acmicpc.net/problem/1181

1181번: 단어 정렬

---

문제 접근

 1. 구조체를 정의해서 입력받는 단어들의 스펠링과 길이를 배열에 저장한다.

 2. 합병정렬을 이용해 배열을 정렬한다.

 3. 정렬된 배열들을 출력할 때 다음에 오는 단어와 같다면 출력하지 않는다.

느낀점

 정렬 파트의 문제이다 보니까 합병정렬과 셸 정렬에 대해서 확실하게 구현할 수 있게 되었다. 사실상 이전 문제와 크게 다를게 없다고 생각했다. 하지만 String에 대한 복습이 확실하게 되었다. 

코드

#include <Stdio.h>
#include <String.h>

typedef struct {
	char string[51];
	int length;
}str;

str sorted[20001];
str arr[20001];

void merge(str arr[], int start, int mid, int last) {
	int i, j, k;
	i = start;
	j = mid + 1;
	k = start;
	while (i <= mid && j <= last) {
		if (arr[i].length < arr[j].length) {
			sorted[k++] = arr[i++];
		}
		else if (arr[i].length > arr[j].length) {
			sorted[k++] = arr[j++];
		}
		else {
			if (strcmp(arr[i].string, arr[j].string) > 0) {
				sorted[k++] = arr[j++];
			}
			else {
				sorted[k++] = arr[i++];
			}
		}
	}
	if (i<=mid) {
		while (i <= mid) {
			sorted[k++] = arr[i++];
		}
	}
	else {
		while (j <= last) {
			sorted[k++] = arr[j++];
		}
	}
	for (i = start; i <= last;i++) {
		arr[i] = sorted[i];
	}
}

void merge_sort(str arr[], int start, int last) {
	int mid;
	if (start < last) {
		mid = (start + last) / 2;
		merge_sort(arr, start, mid);
		merge_sort(arr, mid + 1, last);
		merge(arr, start, mid, last);
	}
}

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%s", &arr[i].string);
		arr[i].length = strlen(arr[i].string);
	}

	merge_sort(arr, 0, n - 1);

	for (int i = 0; i < n;i++) {
		if (strcmp(arr[i].string, arr[i + 1].string) != 0) {
			printf("%s\n", arr[i].string);
		}
	}

	return 0;
}