글 읽기 - C++) 해시 직접 구현 중입니다. 도와주세요ㅠㅠ

lynn29 5년 전 0

C++로 직접 hash 구현 중인데 '틀렸습니다'에서 못 넘어가고 있습니다.

혹시 제가 실수하고 있는 부분이 있을까요? 도와주시면 너무 감사하겠습니다...!

#include <iostream>
#include <stdio.h>
#include <string.h>
#define mod 100019

using namespace std;

typedef struct Node{

    int id;
    char name[25];
    Node* next;

    Node(int n, char *s){
        id = n;
        int i;
        for(i=0; s[i]; i++)
            name[i] = s[i];
        name[i] = 0;
        next = NULL;
    }
}Node;
Node* hashTable[mod];

int MyHash(char *s){

    int ret = 0;
    for(int i=0, k=1; s[i]; i++){
        ret = (ret + k * s[i]) % mod;
        k = (k * 17) % mod;
    }

    return ret;
}

void AddHashTable(Node *node, int key){

    if(hashTable[key] == NULL){
        hashTable[key] = node;
    }
    else{
        node -> next = hashTable[key];
        hashTable[key] = node;
    }
}

bool CompareChar(char *str1, char *str2){

    for(int i=0; str1[i] || str2[i]; i++){
        if(str1[i] != str2[i]) return false;
    }
    return true;
}

int FindHashTable(char *s){

    int key = MyHash(s);

    if(CompareChar(s, hashTable[key] -> name)){
        return hashTable[key] -> id;
    }
    else{
        Node *node = hashTable[key] -> next;

        while(node != NULL){
            if(CompareChar(s, node->name)){
                return node -> id;
            }
            node = node -> next;
        }
    }

    return -1;
}

int CharToString(char *str){

    int ret = 0;
    int tmp = 1;
    for(int i=21; i>=0; i--){
        if(str[i] >= '0' && str[i] <= '9'){
            ret += (str[i] - '0') * tmp;
            tmp *= 10;
        }
    }

    return ret;
}

int main(){

    char tab[100005][25];
    int n, m;
    scanf("%d %d", &n, &m);

    for(int i=1; i<=n; i++){
        char pocket[25];
        scanf("%s", &pocket);

        int j;
        for(j=0; pocket[j]; j++)
            tab[i][j] = pocket[j];
        tab[i][j] = 0;

        int key = MyHash(pocket);
        Node *node = new Node(i, pocket);
        AddHashTable(node, key);
    }

    for(int i=0; i<m; i++){
        char pocket[25];
        scanf("%s", &pocket);

        if(pocket[0] >= '0' && pocket[0] <= '9'){
            int idx = CharToString(pocket);
            printf("%s\n", tab[idx]);
        }

        else
            printf("%d\n", FindHashTable(pocket));
    }
}

seico75 5년 전 0

compareChar 함수의 for문 조건이 좀 이상하네요

lynn29 5년 전 0

자답입니다~

compareChar 함수는 이상 없습니다!

두 char 배열에 값이 있을 때까지 비교해주는 조건문입니다.

hash테이블과 다른 char 배열 초기화로 해결했습니다.

seico75 5년 전 0

제가 익숙하지 않은 방식이어서 이상하게 보였는데,

자세히 보니 좋은 방법이네요. 잘 배우고 갑니다.

문제는 CharToString 함수가 pocket 변수의 뒷부분을 0으로 채우지 않으면 오동작을 하는 것이었나보네요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

C++) 해시 직접 구현 중입니다. 도와주세요ㅠㅠ

lynn29 5년 전 0

seico75 5년 전 0

lynn29 5년 전 0

seico75 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말