백준BOJ 1920 수 찾기(해시 이용, 코드 설명)

https://github.com/o920/baekjoon/blob/master/1920.cpp

o920/baekjoon

해시 문제 찾아서 풀어가지고 해시인 줄은시간 알았지만

시간초과가 나서 결국 구글링을 했고

cin cout 보다 빠른 scanf printf를 쓴다해서 나도 그렇게 함.

 

입력되는 값은 모든 int범위 내 모든 정수이므로  -2,147,483,648 ~ 2,147,483,647 이렇다

총 4,294,967,295개다. 

 

해시함수를 만들때 그냥 저게 딱 열자리니까 반 나누려고 10000으로 나눴다.

그럼 429496개의 테이블을 필요로 한다.

만약 입력된 수가 음수면 절댓값으로 키값을 만들고

양수면 짝수번째 테이블에 저장했다.

 

코드에 주석으로 설명하겠다.

 

 

 

 

#include <iostream>
using namespace std;

struct Node {
	int data;
	Node* next;
};

//해시 테이블 만듦
Node* hTable[214748];//2147483647
//키 값 구하기
int GetKey(int data) {
	if (data < 0) return (data / 10000)*(-1); //음수일때
	else return (data / 10000); //양수일때
}
//해시테이블에 값 넣기
void Insert(int data) {
	int key = GetKey(data); //data의 키 값 구하기
	Node* node = (struct Node*)malloc(sizeof(struct Node)); //node 동적할당
	node->data = data; 
	node->next = NULL;
	Node* origin = hTable[key]; //data가 들어가려는 인덱스에 원래있던 노드
	if (!origin) hTable[key] = node; //그 인덱스에 아무것도 없으면 그냥 node를 넣음
	else { //그 인덱스에 뭐가 있으면 앞에 넣어주면 됨
		node->next = hTable[key]; 
		hTable[key] = node;
	}	
}
//검색
bool Search(int data) {
	int key = GetKey(data); //키 값 구하기
	if (!hTable[key]) return false; //그 인덱스에 엔트리가 어무것도 없으면 false
	if (hTable[key]->data == data) return true; //그 인덱스의 값이 data값과 같으면 true
	else {//아니면 그 인덱스에 있는 노드 다음 노드를 계속 확인해봄
		Node* temp = hTable[key];
		while (temp) {
			if (temp->data == data) return true;
			temp = temp->next;
		}
	}
	return false;
}

int main() {
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		int A;
		cin >> A;
		Insert(A);
	}
	int M;
	cin >> M;
	for (int i = 0; i < M; i++) {
		int check;
        //시간초과 때문에 scanf, printf 사용
		scanf("%d", &check);
		printf("%d\n", Search(check));
	}
}