[C언어] 백준 1181. 단어 정렬

문제

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

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

입력

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

출력

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

구상

20000 x 51 크기의 배열은 선언할 수 있나보다. 선언이 되지 않았다면 2차원 배열을 써서 상당히 복잡한 논리 과정을 거쳐야 하지만 다행히 간단하게 2차원 배열을 선언함으로서 문제를 해결할 수 있다.

 

입력받은 문자열을 qsort를 이용해서 정렬할 것이다. qsort는 정렬 기능을 하는 함수를 직접 만들 수 있어서 활용도가 높다.

 

 

 

qsort와 관련한 설명은 25305. 커트라인 을 참고하면 된다. 

qsort에 인자를 넘긴다. 

 

qsort(arr, size, sizeof(arr[0]), compare);

 

string.h에 있는 strlen, strcmp 함수를 이용해 문제를 해결할 수 있다.

 

우선 길이가 짧은 것부터 정렬해야 한다. strlen 함수는 null문자를 만나기 전까지 문자열의 길이를 재서 반환한다. 

내림차순으로 정렬해야 하니 문자열이 길면 양수를 반환하고, 작으면 음수를 반환한다. 

 //길이순 정렬
	if (strlen((const char*)arg1) > strlen((const char*)arg2)) return 1;
	else if (strlen((const char*)arg1) < strlen((const char*)arg2)) return -1;

그리고 길이가 같은 경우, 코드에서는 if문도 else if문도 만족시키지 않은 나머지 경우에 사전순으로 정렬해야 한다.

이를 위해서 strcmp 함수를 이용한다. 

else return strcmp((char*)arg1, (char*)arg2);

arg1 > agr2  일 때 strcmp의 return value > 0이고, 이를 그대로 반환하면 내림차순으로 정렬할 수 있다. 

 

마지막으로 중복인 문자열을 확인해서 한 번만 출력해야 한다. 

qsort로 배열이 이미 정렬된 상태이니 중복된 문자열은 서로 인접한 위치에 있다.

서로 인접한 두 문자열을 비교하여 일치하지 않을 때만 출력한다.

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

조건 2인 i == size - 1 은 i == 19999가 되어 마지막 요소에 접근할 때, i + 1 == 20000이므로 배열 밖의 쓰레기 값에 접근하게 된다. 이를 피하기 위해 조건으로 넣어줬다.

코드

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


//비교 수행하는 함수, qsort의 4번째 인자
int compare(const void* arg1, const void* arg2) 
{   //길이순 정렬
	if (strlen((const char*)arg1) > strlen((const char*)arg2)) return 1;
	else if (strlen((const char*)arg1) < strlen((const char*)arg2)) return -1;
	//길이 같으면 사전순
	else return strcmp((char*)arg1, (char*)arg2);
} 
int main(void)
{    
	int size, length = 51;
	char arr[20000][51] = { 0 };
	scanf("%d", &size);

	for (int i = 0; i < size; i++)      
		scanf("%s", arr[i]);

	//정렬
	qsort(arr, size, sizeof(arr[0]), compare);
	
	//정렬 후 같은 문자열은 생략하고 출력
	for (int i = 0; i < size; i++) {
		if (strcmp(arr[i], arr[i+1]) != 0 || i == size - 1)
			printf("%s\n", arr[i]);
	}
	return 0;
}