1. 1920 수 찾기

문제 출처 : https://www.acmicpc.net/problem/1920

1920번: 수 찾기

해쉬로 풀이 :

#include<iostream>
#define MAX_HASH 4294967    // int 범위를 1000으로 나눈 값

using namespace std;

typedef struct Node
{
    int id;
    Node* hashNext;
}Node;

Node* hashTable[MAX_HASH];
//해쉬함수
int HASH_KEY(int data){
    int key;
    if(data <0){
        key = data / 1000;
        key *= -1;
    }else{
        key = data / 1000;
        key *= 2;
    }
    return key;
}
void  AddHashData(int key, Node* node)
{
    int hash_key = HASH_KEY(key);
    if (hashTable[hash_key] == NULL)
    {
        hashTable[hash_key] = node;
    }
    else
    {
        node->hashNext = hashTable[hash_key];
        hashTable[hash_key] = node;
    }
}

int FindHashData(int id)
{
    int hash_key = HASH_KEY(id);
    if (hashTable[hash_key] == NULL)
        return 0;   //못찾으면 0
    
    if (hashTable[hash_key]->id == id)
    {
        //        return hashTable[hash_key];
        return 1;   //찾으면 1
    }
    else
    {
        Node* node = hashTable[hash_key];
        while (node->hashNext)
        {
            if (node->hashNext->id == id)
            {
                //                return node->hashNext;
                return 1;
            }
            node = node->hashNext; //찾을 떄까지 검색
        }
    }
    return  0;
}

int main()
{
    int N;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int nInput;
        cin >> nInput;
        Node* node = new Node();
        node->id = nInput;
        node->hashNext = NULL;
        AddHashData(node->id, node);
    }
    //    PrintAllHashData();
    int M;
    cin >> M;
    for (int i = 0; i < M; i++)
    {
        int mInput;
        scanf("%d",&mInput); //시간 초과 때문에 scanf / printf 사용
        printf("%d \n",FindHashData(mInput));
    }
    return 0;   
}