[백준] 1181. 단어 정렬

: solved.ac class 2 - silver 5

 

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

1181번: 단어 정렬

 

 

예제 입력

13
but
i
wont
hesitate
no
more
no
more
it
cannot
wait
im
yours

 

예제 출력

i
im
it
no
but
more
wait
wont
yours
cannot
hesitate

 

정답

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

typedef struct {
	char content[51]; 
	int len;
}string;

int compare(const void* a, const void* b) {
	string* s1 = (string*)a;
	string* s2 = (string*)b;

	if (s1->len < s2->len) return -1;
	else if (s1->len > s2->len) return 1;
	else return strcmp(s1->content, s2->content);
}

int main() {
	int n;
	string* list;

	scanf("%d", &n);
	list = (string*)malloc(n * sizeof(string));

	for (int i = 0; i < n; i++) {
		scanf("%s", list[i].content);
		list[i].len = strlen(list[i].content);
	}

	qsort(list, n, sizeof(string), compare);

	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++) {
			if (strcmp(list[i].content, list[j].content) == 0) {
				strcpy(list[j].content, "\0");
				list[j].len = 0;
			}

		}
	}

	for (int i = 0; i < n; i++) {
		if (list[i].len != 0) printf("%s\n", list[i].content);
	}

	return 0;
}

---

해설

 

: stdlib의 내장함수인 퀵 정렬을 사용하되, compare 함수를 약간 개조하여 이용한다.

 

 

1. 문자열의 내용과 길이를 각각 필드로 나타내는 구조체를 선언한다.

정렬에는 길이와 내용(사전식 정렬을 위해 필요한 아스키코드 값)이 모두 필요하기 때문이다.

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

typedef struct {
	char content[51]; //문자열 내용
	int len; //문자열 길이
}string;

 

2. 퀵 정렬을 위한 compare 함수이다.

정수 정렬에서는 단순히 정수의 크기만을 비교하면 되었으나, 문자열 정렬에서는 길이와 사전식 순서 두 가지를 모두 비교해야 하기 때문에 기본 형태에서 약간의 수정이 필요하다.

• 먼저 len 필드 비교로 문자열의 길이를 비교한다.
• 문자열의 길이가 같은 경우 strcmp 함수로 문자열의 아스키코드 값을 비교한다. strcmp 함수는 아스키코드 값을 비교하여 다른 경우는 -1이나 1, 같은 경우는 0을 리턴하기 때문에 사전식 비교가 필요한 경우에 사용하면 유용하다.

int compare(const void* a, const void* b) {
	string* s1 = (string*)a;
	string* s2 = (string*)b;

	if (s1->len < s2->len) return -1;
	else if (s1->len > s2->len) return 1;
	else return strcmp(s1->content, s2->content);
	//strcmp로 문자열의 아스키코드 비교
}

 

 

3. 구조체 배열을 포인터 형으로 선언해 주고 동적 할당으로 입력받은 n만큼의 공간을 할당해 준다.

(무작정 최대 갯수의 배열을 선언해 주면 에러가 발생한다.)

content 필드에 내용을 입력받음과 동시에 strlen 함수로 길이를 구해 len 필드에 입력해주도록 한다.

int main() {
	int n;
	string* list;

	scanf("%d", &n);
	list = (string*)malloc(n * sizeof(string));

	for (int i = 0; i < n; i++) {
		scanf("%s", list[i].content); //단어 내용 입력
		list[i].len = strlen(list[i].content);
		//단어 길이 저장
	}

 

4. qsort 함수로 길이/사전식 정렬을 해준 뒤, 중복을 제거하는 작업을 한다.

같은 단어를 만나면 중복된 해당 단어의 내용을 null 문자로 바꾸고 len을 0으로 만들어 없는 단어로 처리한다.

이후 정렬된 단어를 출력할 때 단어의 len이 0이 아닌지 검사하여, 0이라면 해당 단어는 생략하고 출력하도록 한다.

	qsort(list, n, sizeof(string), compare);

	for (int i = 0; i < n - 1; i++) { //중복 제거
		for (int j = i + 1; j < n; j++) {
			//단어 중복이 발견되면
			if (strcmp(list[i].content, list[j].content) == 0) {
				strcpy(list[j].content, "\0");
				//중복된 단어 내용을 널문자로 바꾸고
				list[j].len = 0; //길이는 0 처리
			}

		}
	}

	for (int i = 0; i < n; i++) {
		if (list[i].len != 0) printf("%s\n", list[i].content);
	}

	return 0;
}