/<> 백준 17219번 : 비밀번호 찾기 (C언어)

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

 

 

사이트 주소와 비밀번호를 저장하는 문자열 배열을 만들어서 모두 저장 후, 찾고자 하는 비밀번호를 하나하나 사이트를 탐색하면 시간이 매우 비효율적입니다. 이 경우에 해시 함수를 사용하면 됩니다. 해시 함수란 임의의 값을 고정된 값으로 출력받는 함수로 데이터 리딩 속도가 아주 높습니다. 시간 복잡도를 이론상 O(1)을 목표로 하는 함수이기 때문이죠. 해시 함수는 여러 가지가 있는데, 그 중 하나인 djb2함수를 사용할 겁니다. 이는 크기가 큰 소수를 이용해 특정 문자열을 고유한 값으로 반환합니다. 해당 함수의 코드는 다음과 같습니다.

 

unsigned int func(const char *str) {
        unsigned int hash = 5381;
        int c;
        while(c = *str++) {
                hash = ((hash << 5) + hash) + c;
        }
        return hash;
}

 

 

1. 사이트의 주소와 비밀번호를 입력받습니다.

 

2. 해시 함수를 통해 저장하는 배열의 고유 인덱스 값을 구합니다.

 

3. 구한 인덱스에 주소와 비밀번호를 저장합니다.

 

4. 비밀번호를 구하고 싶은 사이트를 해시 함수를 통해 고유 인덱스 값을 얻어서 그 비밀번호인 배열의 값을 구합니다.

 

 

<코드>

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

typedef struct site {
        char name[21];
        char password[21];
} site;

unsigned int func(const char *str) {
        unsigned int hash = 5381;
        int c;
        while(c = *str++) {
                hash = ((hash << 5) + hash) + c;
        }
        return hash;
}

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

        site site[2 * n];
        for(int i = 0; i < n; i++) {
                char n_name[21], n_password[21];
                scanf("%s %s", n_name, n_password);
                unsigned int val = func(n_name) % (2 * n);
                while(site[val].name[0] != '\0') val = (val + 1) % (2 * n);
                strcpy(site[val].name, n_name);
                strcpy(site[val].password, n_password);
        }

        for(int i = 0; i < m; i++) {
                char f_name[21];
                scanf("%s", f_name);
                unsigned int val = func(f_name) % (2 * n);
                while(strcmp(site[val].name, f_name) != 0) val = (val + 1) % (2 * n);
                printf("%s\n", site[val].password);
        }
        return 0;
}