[Baekjoon] Class2 03 - 단어 정렬[1181]

단어 정렬 [1181번]

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

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

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

생각해볼점

퀵 정렬(Quick sort)

위키피디아 링크
시각적으로 이해 가능한 링크
분할 정복을 통해 정렬하는 방법이다.

1. 리스트에서 하나의 원소를 골라 피벗(pivot)으로 정한다.
2. 피벗을 기준으로 앞쪽에는 피벗보다 작은 값이, 뒤쪽에는 큰 값이 오도록 리스트를 나눈다.
3. 나누어진 리스트에 대해서 앞의 과정을 반복한다. 반복은 리스트의 크기가 0 또는 1이 될때까지 수행된다.
   이 과정을 글로 이해하기는 쉽지 않았다. 그림이나 영상을 보고 익히는게 가장 좋은 방법인 듯 하다.

• 일반적인 경우 : 시간복잡도 O(nlogn), 공간복잡도 O(logn)
• 최악의 경우 : 시간복잡도 O(n^2), 공간복잡도 O(n)
  결정한 피벗의 위치에 따라 복잡도가 달라진다. 다만 C에 내장되어있는 qsort() 함수와 같은 경우 효율적으로 작동하도록 설계되어있어 대부분 일반적인 경우의 복잡도를 따른다고 한다. 따라서 직접 구현한 퀵 정렬과는 차이가 있을 수밖에 없다.

코드 구현

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

static void swap(char **str1, char **str2)
{
	char	*temp;

	temp = *str1;
	*str1 = *str2;
	*str2 = temp;
}

//리스트의 가장 왼쪽 원소를 피벗으로 두고 정렬
static void quick_sort(char **word, int left, int right)
{
	int		low = left + 1, high = right, pivot = left;

	if (left < right)
	{
		while (low <= high)
		{
			while (strlen(word[low]) <= strlen(word[pivot]) && low < right)
			{
				if (strlen(word[low]) == strlen(word[pivot]) 
					&& strcmp(word[low], word[pivot]) > 0)
					break;
				low++;
			}

			while (strlen(word[high]) >= strlen(word[pivot]) && high > left)
			{
				if (strlen(word[high]) == strlen(word[pivot]) 
					&& strcmp(word[high], word[pivot]) < 0)
						break;
				high--;
			}

			if (low >= high)
				break;

			swap(&word[low], &word[high]);
			low++;
			high--;
		}

		swap(&word[left], &word[high]);
		quick_sort(word, left, high - 1);
		quick_sort(word, low, right);
	}
}

int main()
{
	int		num, idx = 0;
	char	**word, temp[50];

	scanf("%d", &num);
	word = (char **)malloc((num + 1) * sizeof(char *));
	
	while (idx < num)
	{	
		scanf("%s", temp);
		word[idx] = (char *)malloc((strlen(temp) + 1) * sizeof(char));
		strcpy(word[idx++], temp); 
	}
	word[idx] = NULL;

	quick_sort(word, 0, num - 1);
	// 퀵 정렬으로 단어 정렬

	idx = -1;
	while (word[++idx])
	{
		if (idx == 0)
			printf("%s\n", word[idx]);
		else
		{
			if (strcmp(word[idx], word[idx - 1])) // 중복 단어 제외하고 출력
				printf("%s\n", word[idx]);
		}
	}
	
	idx = -1;
	while (++idx < num)
		free(word[idx])
	free(word);

	return (0);
}