문제
알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.
- 길이가 짧은 것부터
- 길이가 같으면 사전 순으로
입력
첫째 줄에 단어의 개수 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;
}