1764번 듣보잡 - 해시, 정렬, 이분탐색

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

#define MAX_TABLE 1000003  // 소수

typedef unsigned long long ull;

typedef struct _DIC
{
    char name[21];
    
    struct _DIC* next;
} DIC;

DIC HASH_TABLE[MAX_TABLE];
DIC ary[MAX_TABLE];
DIC* memo[MAX_TABLE];

ull hash(char* str)
{
    ull hash = 5381;
    char c;
    
    while(c = *(str++))
        hash = ((hash<<5) + hash + c) % MAX_TABLE;  //해시 형성 함수
    
    return hash % MAX_TABLE;
}

void quickSort(DIC* arr[], int l, int r)  //정렬
{
    int ql = l, qr = r;
    DIC* pivot = arr[(ql+qr)/2];
    DIC* temp;
    
    while(ql <= qr) {
        while(strcmp(arr[ql]->name, pivot->name) < 0 && ql<=r)
            ql++;
        while(strcmp(arr[qr]->name, pivot->name) > 0 && qr>=l)
            qr--;
        if(ql<=qr) {
            temp = arr[ql];
            arr[ql] = arr[qr];
            arr[qr] = temp;
            ql++, qr--;
        }
    }
    
    if(l < qr)
        quickSort(arr, l, qr);
    if(ql < r)
        quickSort(arr, ql, r);
}

int main()
{
    int N, M;
    int cnt=0;
    int i;
    
    scanf("%d %d", &N, &M);
    
    for(i=0; i<N; i++) {
        scanf("%s", ary[i].name);
        
        ull h = hash(ary[i].name);  //이름에 해당하는 해시를 해시테이블에 저장
        
        ary[i].next = HASH_TABLE[h].next;
        HASH_TABLE[h].next = &ary[i];
    }
    
    for(i=0; i<M; i++) {
        char input[21];
        
        scanf("%s", input);
        
        ull h = hash(input);
        
        DIC* node = HASH_TABLE[h].next;
        
        while(node && strcmp(node->name, input))  //같은 해시를 가진 것끼리 비교해서 저장
            node = node->next;
        
        if(node)
            memo[cnt++] = node;
    }
    
    printf("%d\n", cnt);
    quickSort(memo, 0, cnt-1);  //찾은 문자열을 정렬
    for(i=0; i<cnt; i++)
        printf("%s\n", memo[i]->name);
    
    return 0;
}

 

해시를 쓰고 정렬을 쓰면 쉽게 풀 수 있을 것 같아서 코드를 짰다. 풀고 나서 보니 더 짧은 시간으로 푼 사람이 맣아서 코드를 봤다.

1. 입력받은 단어들을 qsort()로 정렬한다.

2. 정렬한 단어들을 bsearch() 이분탐색으로 찾아낸다.

3. qsort()로 한 번 더 정렬한 후 출력한다.

 

밑에 참고한 사이트와 코드가 있다.

 

 

 

<C언어 퀵 정렬 구현>

https://prosto.tistory.com/177

퀵 정렬(Quick Sort) - C언어/자료구조

<bsearch()>

https://norux.me/20

C언어 bsearch() - 이진탐색 함수

 

<함수 포인터>

https://dojang.io/mod/page/view.php?id=593 

C 언어 코딩 도장: 68.2 반환값과 매개변수가 있는 함수 포인터 만들기

 

<qsort()>

https://dojang.io/mod/page/view.php?id=638 

C 언어 코딩 도장: 73.2 퀵 정렬 함수 사용하기

 

<참고한 코드(문제를 풀어야 볼 수 있습니다.)>

https://www.acmicpc.net/source/680651

로그인

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.