1181: 단어 정렬

-Class2 : Silver 5

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

1181번: 단어 정렬

 

-결과

 

-코드

#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;
}

 

-풀이

이 문제는 시간 복잡도가 O(n log n)인 merge sort로 푸는 문제이다.

우선 임시로 배열을 할당하여 단어들을 저장한 후에, if - else문을 이용하여 길이가 작은 단어부터 긴 단어 순으로 정렬하도록 하고, 만약 길이가 같은 단어들의 경우에는 사전순으로 정렬하도록 작성한다.

main 함수에는 for문을 사용하여 만약 같은 단어가 반복되는 경우에는 중복을 피하게끔 작성한다.