백준 1181 - 단어 정렬

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

qsort 를 사용해서 쌈뽕하게 정렬해주면 된다

🔍 qsort()란?

qsort() 함수는 C 언어에서 배열을 정렬할 때 사용하는 표준 라이브러리 함수로, 사용자가 비교 기준을 자유롭게 정의할 수 있게 도와준다
비교 기준은 int compare(const void* a, const void* b) 형태의 함수를 넘겨주면 된다

---

✅ 오름차순 정렬용 compare 함수

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int compare(const void *a, const void *b)
{
    int v1 = *(const int *)a;
    int v2 = *(const int *)b;

    return (v1 > v2) - (v1 < v2);
}

📌 설명:

• a와 b는 void* 형이기 때문에 먼저 int*로 바꿔준다

• * (int*)a는 포인터가 가리키는 정수 값을 가져옵니다.

• 두 값의 차를 리턴함으로써 정렬 기준이 됩니다.

  • 음수: a가 먼저
  • 0: 순서 동일
  • 양수: b가 먼저

💡 예:

int arr[] = {3, 1, 4, 2};
qsort(arr, 4, sizeof(int), compare);

→ 출력: 1 2 3 4

---

✅ 이 문제에서 사용한 문자열 배열 정렬용 compare 함수

int compare(const void *a, const void *b){
    if(strlen((const char *)a) != strlen((const char *)b)){
        return strlen((const char *)a) - strlen((const char *)b);
    }
    else {
        return strcmp((const char *)a, (const char *)b);
    }
}

📌 설명:

• char arr[][51]처럼 문자열 배열을 정렬할 때 사용
• (const char *)a는 char 배열 한 줄의 시작 주소를 문자열로 캐스팅
• 먼저 문자열의 길이를 비교해 짧은 문자열이 먼저 오도록 정렬
• 만약 길이가 같다면 strcmp()를 사용해 사전순 정렬

💡 예:

char arr[5][51] = {"apple", "hi", "zebra", "dog", "cat"};
qsort(arr, 5, sizeof(arr[0]), compare);

→ 출력 순서:

hi
cat
dog
apple
zebra

---

❗ 왜 *(const char *)a라고 하면 안될까?

문자열 비교에서는 *(const char *)a를 쓰면 안 되는데, 그 이유는 * 연산을 하면 문자 하나(char)만 꺼내게 되기 때문이다
문자열 함수인 strlen()이나 strcmp()는 문자열 전체의 주소를 필요로 하므로 (const char *)a처럼 포인터만 넘겨야 한다

최종 코드

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

int compare(const void *a, const void *b){
    if(strlen((const char *)a) != strlen((const char *)b)){
        return strlen((const char *)a) - strlen((const char *)b);
    }
    else {
            return strcmp((const char *)a,(const char *)b);
    }
}

int main()
{
    int N;
    scanf("%d", &N);

    char arr[20000][51];

    for (int i = 0; i < N; i++)
    {
        scanf("%s", &arr[i]);
    }
    qsort(arr, N, 51, compare);
    
    for (int i = 0; i < N-1; i++)
    {
        if(strcmp(arr[i],arr[i+1])!=0){
            printf("%s\n", arr[i]);
        }
    }
     printf("%s", arr[N-1]);
}

qsort 함수를 사용해 문자열 배열을 **길이순(짧은 → 긴)**으로 정렬하고, 길이가 같을 경우에는 사전순으로 정렬하도록 compare 함수를 작성했다

이후 정렬된 배열을 순회하면서 strcmp(arr[i], arr[i+1]) != 0 조건을 통해 중복된 단어는 출력하지 않도록 처리하였다

이 때, arr[i+1]에 접근하기 때문에 반복문 범위를 i < N으로 하면 배열 범위를 초과할 수 있으므로, for (int i = 0; i < N - 1; i++)로 조건을 설정하였다

마지막 단어는 비교 대상이 없기 때문에 printf("%s\n", arr[N - 1]);을 통해 한 번 더 출력해주었다

---

🐷 숫자 정렬하는 다른 방법

qsort 는 너무 느리므로 계수 정렬을 사용하여 잽싸게 풀어보고자 한다

#include <stdio.h>

int main()
{
    int N, num, arr[10001]; // N: 입력 개수, num: 입력 받은 숫자 저장, arr: 각 숫자의 등장 횟수 저장용 배열

    scanf("%d", &N);

    // arr 배열 초기화 (모든 값을 0으로 설정)
    for (int i = 0; i < 10001; i++)
    {
        arr[i] = 0;
    }

    // N개의 숫자를 입력받고, 해당 숫자의 인덱스에 개수를 증가시킴
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &num);
        arr[num]++;        // 해당 숫자가 등장한 횟수를 기록
    }

    // 정렬된 형태로 출력
    // arr[i]가 0보다 크면, i를 arr[i]번 출력함
    for (int i = 0; i < 10001; i++)
    {
        for (int j = 0; j < arr[i]; j++)
        {
            printf("%d\n", i);
        }
    }

    return 0;
}