[C]백준 12.정렬: 1181

백준 1181

내코드

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

int sorted[20001][51];
void merge(char list[][51], int left, int mid, int right) {
	int i, j, k, l;
	i = left;
	j = mid + 1;
	k = left;
	while (i <= mid && j <= right) {
		if (strlen(list[i]) < strlen(list[j])) {
			strcpy(sorted[k++], list[i++]);
		}
		else if (strlen(list[i]) > strlen(list[j])) {
			strcpy(sorted[k++], list[j++]);
		}
		else {
			if (strcmp(list[i], list[j]) == 0) {
				strcpy(sorted[k++], list[i++]);
				strcpy(sorted[k++], list[j++]);
			}
			else if (strcmp(list[i], list[j]) < 0) {
				strcpy(sorted[k++], list[i++]);
			}
			else if (strcmp(list[i], list[j]) > 0) {
				strcpy(sorted[k++], list[j++]);
			}
		}
	}
	if (i > mid) {
		for (l = j; l <= right; l++) {
			strcpy(sorted[k++], list[l]);
		}
	}
	else {
		for (l = i; l <= mid; l++) {
			strcpy(sorted[k++], list[l]);
		}
	}
	for (l = left; l <= right; l++) {
		strcpy(list[l], sorted[l]);
	}
}

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

int main() {
	int n;
	scanf("%d", &n);
	char str[20001][51];
	for (int i = 0; i < n; i++) {
		scanf("%s", str[i]);
	}

	merge_sort(str, 0, n - 1);
	for (int i = 0; i < n; i++) {
		if (i != (n - 1) && strcmp(str[i], str[i + 1]) == 0)
			continue;
		else
			printf("%s\n", str[i]);
	}


	return 0;
}

기존의 병합정렬 코드를 수정하여 풀었다.
정렬 조건이 길이가 짧은 것 부터, 길이가 같다면 알파벳 사전 순으로 정렬하는 것이기에 strlen함수를 이용해 길이를 비교하여 길이가 짧은 단어를 먼저 sorted 배열에 넣었고 만약 길이가 같다면 strcmp함수를 이용해 알파벳 사전 순으로 먼저 위치한 단어를 sorted 배열에 넣었다. 또 만약 단어가 같아서 strcmp함수의 결과값이 0이라면 두 단어 모두 sorted 배열에 넣었다.
위의 방식으로 정렬한 후 배열은 길이 순, 알파벳 사전 순으로 정렬되지만 중복된 단어가 존재한다.
따라서 반복문을 돌려 만약 해당 순서 다음 단어와 비교했을 때 같은 단어라면 출력하지 않고 그외의 경우엔 출력하는 방식으로 코드를 작성했다.

 

strcmp함수는 운영체제에 따라서 동작방식이 조금 다르다고 한다. 그래서 window(visual studio)에서는 문자열이 다르면 1또는 -1을 반환하지만 리눅스와 OS X에서는 ASCII코드 값의 차이를 반환한다고 한다. 그래서 strcmp함수의 반환값을 판단할때는 1또는 -1로 값을 특정하지 않고 범위를 통해 양수, 0, 음수로 판단하는게 좋다고 한다.

 

https://dojang.io/mod/page/view.php?id=346 

C 언어 코딩 도장: 41.2 문자열 비교하기