백준 1181번

단어 정렬

시간 제한 메모리 제한

2 초 256 MB

문제

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

1.길이가 짧은 것부터

2.길이가 같으면 사전 순으로

입력

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

출력

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

해설

이 문제 같은 경우 qsort와 strcmp을 이용해서 풀었다. qsort는 pivot을 정하고 pivot보다 작은 값들을 pivot의 왼쪽 pivot보다 큰 값들은 pivot의 오른쪽으로 위치시키고 pivot의 왼쪽 값들과 오른쪽 값들을 각각 따로 또 재귀를 통해 분할정복한다. 이것을 이용해 정렬하는 시간을 줄일 수 있다 그다음 strcmp는 함수가 앞에서 부터 각각 문자를 비교할때, 아스키 코드값으로 비교를 할 수 있다.

문자열 2차원 배열을 통해 문자열을 받아 오고 qsort를 이용해 문자길이를 비교해 정렬 후 같은 문자길이는 strcmp를 이용해 문자를 비교해서 정렬을 한다 출력시 같은 문자가 나올 경우 이번 출력을 무시한다.

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

int compare(const void* a, const void* b) {
	if (strlen((char*)a) > strlen((char*)b))
	{
		return 1;
	}
	if (strlen((char*)a) < strlen((char*)b))
	{
		return -1;
	}
	if (strlen((char*)a) == strlen((char*)b))//문자열 길이가 같은때 사전순으로
	{
		return strcmp((char*)a, (char*)b);
	}
}

int main() {
	int z;
	scanf("%d", &z);
	char a[z][51];
	for (int i = 0; i < z; i++)//문자열 입력받기
	{
		scanf("%s", a[i]);
	}
	qsort(a, sizeof(a) / sizeof(a[0]), sizeof(a[0]), compare);//퀵소트 문자열 a
	for (int i = 0; i < z; i++)//문자열 출력
	{
		if (strcmp(a[i], a[i+1]) != 0)//다음 출력과 같지 않을경우 출력
		{
			printf("%s\n", a[i]);
		}
	}
}

Written on September 23, 2022