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

 

링크

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

1181번: 단어 정렬

 

 

 

 

 

문제

---

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

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

단, 중복된 단어는 하나만 남기고 제거해야 한다.

 

 

 

 

 

입력

---

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

 

 

 

출력

---

조건에 따라 정렬하여 단어들을 출력한다.

 

 

 

예제 입력 1

---

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

 

예제 출력 1

---

i
im
it
no
but
more
wait
wont
yours
cannot
hesitate

 

 

 

 

아이디어 스케치

---

- 단어의 개수는 최대 20000개, 주어지는 문자열의 길이는 50을 넘지 않으므로 이 조건에 맞는 2차원 배열을 이용하면 된다.

- 길이가 짧은 순으로, 길이가 같으면 사전 순으로 정렬하는 문제이므로, 퀵 정렬을 이용하여 오름차순 정렬을 수행하면 된다.

- 중복된 단어는 하나만 남기고 제거해야 하므로 출력할 때 비교함수를 이용하여 중복을 제거하고 출력하면 된다.

 

 

 

 

 

코드 분할 설명

---

scanf("%d", &size);

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

qsort(arr, size, sizeof(arr[0]), compare);		//퀵정렬

 

- 단어의 갯수를 입력받은 후 단어들을 입력받는다.
- 단어를 입력받은 배열을 퀵정렬을 이용하여 조건에 맞게 정렬한다.

 

 

 

 

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);		//길이가 같을 때는 사전순으로 정렬
}

 

- 이 문제의 핵심이다.
- 먼저 단어의 길이순으로 오름차순 정렬을 수행한다.
- 길이가 같을 때는 사전순으로 정렬한다.
- 이때 return strcmp((char)arg1, (char)arg2); 이렇게 쓴 이유는 strcmp함수는 인자로 a,b 두개를 받으며 a가 b보다 클 때 1을 반환하는 함수이다. 문자열의 크기를 비교하는 기준되는 값은 아스키 코드값인데 알파벳의 아스키 코드 값은 사전순으로 정렬되어 있어 값이 작으면 사전순으로 앞쪽, 값이 크면 사전순으로 뒷쪽에 위치한다.

 

 

 

 

 

전체 코드

---

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 51

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][SIZE] = { 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;
}

 

 

 

 

 

 

 

제출 결과

---