c언어 28446번 볼링공 찾아주기 (백준)

#include <stdio.h>
#define M 1000000007
#define m 600000
#define p 257

long long hash(int s) {
	long long a=0,b=1,c=0,i=4;
	while(i--) {
		c=s&0xFF;
		a=(a+c*b)%M;
		b=(b*p)%M;
		s>>=8;
	}
	 return a;
}

int main() {
	int n,i,a,b,c,t[m]={},T[m]={};
	long long v;
	scanf("%d",&n);
	for(i=0;i<n;i++) {
		scanf("%d %d",&a,&b);
		if(a==1) {
			scanf("%d",&c);
			v=hash(c)%m;
			while(t[v]) {
				++v;
				if(v==m) v=0;
			} t[v]=b;T[v]=c;
		}
		else {
			v=hash(b)%m;
			while(T[v]!=b) {
				++v;
				if(v==m) v=0;
			} printf("%d\n",t[v]);
		}
	}
}

 

풀이 : key의 중복이 없는것을 이용한 해쉬를 이용한 map

 

1. 해쉬값 만들기

문자열을 해쉬값으로 만들었을 때는, 한 문자씩 -'a'+1 을 하면서 값을 구했다면, 정수형의 경우 & 1111 (비트).. 이런식으로 1로 이루어진 값과 and 비트 연산을 하여, 특정 부분의 (위의 코드에선 8비트) 숫자만을 가져올 수 있습니다. 범위는 0~255 이므로 해쉬 값 계산에서 사용할 소수는 255보다 큰 소수를 곱해주어야 합니다. (위의 코드에선 257)

 

2. map에 삽입하기

t[]는 w무게의 해쉬값에 % m을 한 값을 key값으로 x번 사물함을 value로 하는 배열입니다.

T[]는 w무게의 해쉬값에 % m을 한 값을 key값으로 w무게를 value로 하는 배열입니다 (이건 map에서 꺼낼때 정말 맞는지를 확인하기위한 용도입니다) (중요한 것은 초기화를 0으로 해주어야 합니다)

 

w무게는 중복이 없다고 나왔으므로, 충돌 여부는, 해쉬테이블이 비어져 있는가만 바라보면 됩니다. 만약 있다면 +1 을 하고, 비어있다면 거기에 집어넣습니다.

 

3. map에서 꺼내기

이번에도 해쉬값을 구해서 % m을 한 다음, 이것으로 해쉬테이블에 접근합니다. 내가 원하는 값이 맞는지를 확인하는 방법은 (문제 조건에서 삽입이 되지 않은 값을 꺼내는 경우는 없다고 나와있습니다) T[]에 접근하여, 입력받은 w무게와 테이블에 있는 w무게를 비교하여 맞다면, 동일한 해쉬값%m으로 t[]값을 출력하면 된다.

 

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