문자열에서 정수로 바꾸기. strcmp 없이 정수로 비교하기

long long의 자료형으로 소문자만 들어오는 문자열을 몇개까지 고유의 값으로 표현할 수 있을까?

 

정답은 12개 이다.

 

왜냐하면 영어 소문자는 26개이고, 5비트로 표현할 수 있는 개수는 32개이다.

그러면 64bit / 5bit = 12개이기 때문이다.

 

사실 남는 4bit가 아까워서 << 5 대신에, + 27을 사용할 수도 있다. 하지만 복잡하기도 하고 << 연산자가 속도도 더 빠르기 때문에 <<를 쓰자.

 

근데 내가 적었던 말 중에 잘 못된게 있다. 그것은 바로 long long이 아니라 unsigned long long을 써야 64bit인 것이다.

unsigned를 써줌으로서 맨 앞의 MSB(부호비트를) 사용하지 않게 된다. 그래야 64bit 풀로 사용할 수 있다.

 

 

기본적인 형태이다.

static long long srtToLL(const char* s)
{
	long long h = 0;
	for (int i = 0; s[i]; i++) {
		h = (h << 5) + s[i] - 'a' + 1;
	}
    return h;
}

영어 소문자 문자열 10자리가 있다고 하면,

long long 으로 다 표현할 수 있다.

영어 소문자는 26개이기 때문에 5번씩 shift해주면 된다.

그리고 반드시 'a'를 빼고 +1을 해주어야 한다.

'a'를 빼지 않을 시 offset문제로 인하여 overflow가 발생할 수 있다.

1을 + 하지 않을 시 a와 aaa를 구분할 수 없게되는 문제가 발생한다.

 

 

그럼 만약 문자열을 길이가 10이 넘어가서 한 개의 정수형으로 표현하지 못한다면?

간단하다. 그냥 배열로 만들어버리면 된다.

대신 배열을 return 하기는 애매하니 직접 값을 받아와서 배열의 값을 바꾸면 된다.

static void strToLL(const char* s, long long h[3])
{
	h[0] = h[1] = h[2] = 0;
	for (int i = 0, c = 0; s[i]; i++) {
		h[c] = (h[c] << 5) + s[i] - 'a' + 1;

		if ((i + 1) % 10 == 0)
			++c;
	}
	int idx = (int)((((h[0] + h[1]) % MAX_TABLE) + h[2]) % MAX_TABLE);
}

이런식으로, 첫번째 long long이 꽉 차게되면 c를 증가 시켜서 다시 새로운 long long에 채워나가면 된다.

그리고 아래의 idx는 3개의 고유한 long long을 가지고 hash Index를 만드는 식이다.

 

h[0] + h[1] + h[2] 를 하면 overflow가 발생할 수 있으므로, 각 더하기 연산마다 %를 해준다.

 

 

그럼 만약 대소문자, 특수문자까지 섞였는데, 문자열도 long long으로 표시를 못한다면?

static void strToLL(const char* s, long long h[3])
{
	h[0] = h[1] = h[2] = 0;
	for (int i = 0, c = 0; s[i]; i++) {
		if (s[i] >= 'a' && s[i] <= 'z')
			h[c] = (h[c] << 6) + s[i] - 'a' + 1;
		else if (s[i] >= 'A' && s[i] <= 'Z')
			h[c] = (h[c] << 6) + s[i] - 'A' + 27;
		else if (s[i] == '.')
			h[c] = (h[c] << 6) + s[i] - '.' + 53;

		if ((i + 1) % 10 == 0)
			++c;
            
	}
    
	int idx = (int)((((h[0] + h[1]) % MAX_TABLE) + h[2]) % MAX_TABLE);
}

이렇게 위의 두 코드를 섞어서 사용하면 된다.