[알고리즘] 백준 1620번 - 나는야 포켓몬 마스터 이다솜

#라이브러리 없이 코딩하기

#이지만 atoi는 직접 구현하니 시간초과라

#라이브러리 사용

 

 

구현 알고리즘

• Hash

 

생각해 볼 거리

• 이중 for loop 안에서 break를 사용하면 왜 실행 시간이  8ms 늘어날까?

• 시간 초과 나지 않도록 atoi 직접 구현해보기

 

소스 코드

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

#define MAX_TABLE 100017
#define MAX_NAME 21

struct Hash {
    char name[MAX_NAME];
    Hash* next;
    unsigned long int idx;
} h[MAX_TABLE], * ht[MAX_TABLE];
unsigned int h_idx = 1;

unsigned long getHash(const char* str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
    {
        hash = (((hash << 5) + hash) + c);
    }

    return hash;
}

void mstrcpy(char* dst, const char* src) {
    while (*src)
        *dst++ = *src++;
    *dst = '\0';
}

int mstrcmp(const char* a, const char* b) {
    while (*a && *a == *b) {
        ++a; ++b;
    }
    return *a - *b;
}

int main() {

    int m, n; // >=1 , <= 100,000
    scanf("%d %d", &m, &n);

    char name[MAX_NAME];
    for (int i = 1; i <= m; i++) {
        scanf("%s", name);

        unsigned long key = getHash(name) % MAX_TABLE;

        Hash* newH = &h[h_idx++];
        newH->idx = i;
        mstrcpy(newH->name, name);

        newH->next = ht[key];
        ht[key] = newH;
    }

    for (int i = 0; i < n; i++) {
        scanf("%s", name);

        if ('0' <= name[0] && name[0] <= '9') {
            printf("%s\n", h[atoi(name)].name);
        }
        else {
            unsigned long key = getHash(name) % MAX_TABLE;

            for (Hash* cur = ht[key]; cur != 0; cur = cur->next) {
                if (!mstrcmp(cur->name, name)) {
                    printf("%d\n", cur->idx);
                }
            }
        }
    }
}