[Python] 13783번: Hashing 풀이

 

 

 

---

백준 풀이

13783번: Hashing 풀이

---

 

문제 Link : https://www.acmicpc.net/problem/13783

13783번: Hashing

 

문제

A string hashing function is an algorithm that turns arbitrary strings into numbers. 
If S is a string of length N,  one simple hashing function is 

`S[0] * 31^(N‐1) + S[1] * 31^(N‐2) + ... + S[N‐1]`
where S[i] is the ASCII code of the i'th character and ^ indicates exponentiation. 
The computation is done using big integer arithmetic (it never overflows). 

Note: In most programming languages ^ does NOT perform exponentiation. 

Here are some example strings and the corresponding values computed by this hashing function: 

"ab" (N = 2, ASCII codes of characters: 97 98) 
hash = 97 * 31 + 98 = 3105 
"Hi!" (N = 3, ASCII codes of characters: 72 105 33) 
hash = 72 * 31^2 + 105 * 31 + 33 = 72480 
"IJ!" (N = 3, ASCII codes of characters: 73 74 33). 
hash = 73 * 31^2 + 74 * 31 + 33 = 72480 
Sometimes different strings have the same hash (like the second and third strings above).  

A string is considered valid if all its characters have ASCII codes in the range 32 to 126 inclusive. 

Your task is to count the number of valid strings that have the same hash as a given input string.

 

 

결론적으로 해야 할 일은 두 가지입니다.

1. 다음과 같은 식의 해시 함수를 통해 해시 값 추출

S[0] * 31^(N‐1) + S[1] * 31^(N‐2) + ... + S[N‐1]

2. 1번의 결과로 구한 해시 값과 충돌을 발생하는 케이스 구하기

• 문자의 범위는 아스키 코드 기준 32이상 126 이하
• modulo 1,000,000,007 (10^9 + 7) 안에서 가정
• 자기 자신 포함

 

좀 복잡한데, 우선 1번은 간단하니 먼저 구현해보았습니다.

def get_hash(n_list):
    hash_val = 0
    n = len(n_list)
    for i in range(n):
        hash_val += n_list[i]*(31**(n-i-1))
    return hash_val % 1000000007

 

다음은 이제 hash collision을 찾는 건데, 이게 좀 까다롭습니다.

문제를 풀 당시 고민한 부분은 다음과 같습니다.

• hash collision을 찾는 문자열의 길이가 정해져 있지 않음

처음 작성한 코드는 다음과 같은데, 원래는 메모리 문제가 발생했습니다.

def get_hash_crash(hash_val):
    string_len, result = 1, 0
    while True:
        min_val = sum([31**i for i in range(string_len)])
        if min_val > hash_val:
            return result
        n_list = [i for i in product(list(range(32, 127)), repeat=string_len)]
        for i in range(len(n_list)):
            hash_cal = get_hash(list(n_list[i]))
            if hash_cal == hash_val:
                result += 1
        string_len += 1

여기가 문제의 부분이였는데, 원래는 각 문자열의 해시 최솟값을 비교해서 그 값이 더 클 경우 그때 무한루프를 탈출하도록 했는데, 무한루프가 메모리를 너무 많이 잡아먹고 있는 것 같아 구조를 조금 바꿨습니다.

 

글로 설명하자면 다음과 같습니다.

1. 각 문자열의 해시 최솟값을 통해 비교할 수 있는 문자 길이의 최댓값(string_len)을 구함
2. 구한 문자 길이의 최댓값(string_len)을 통해 모든 경우의 수의 해시 값을 구하고, 기존의 해시 값과 비교하여 hash collision 발견

핵심 코드는 다음과 같습니다.

def get_max_string_len(hash_val):
    for string_len in range(30):
        min_val = sum([31**i for i in range(string_len+1)])
        if min_val > hash_val:
            return string_len

def get_hash_crash(hash_val):
    result = 0
    string_len = get_max_string_len(hash_val)
    #print(string_len)
    for j in range(string_len):
        n_list = [i for i in product(list(range(32, 127)), repeat=j)]
        for i in range(len(n_list)):
            hash_cal = get_hash(list(n_list[i]))
            if hash_cal == hash_val:
                result += 1
    return result

 

get_max_string_len함수를 통해 먼저 string의 길이를 구하는 방식으로 문제를 풀었습니다.

 

메모리/코드 길이를 통해 볼 수 있는 python+실력의 한계

3등! 좋아요~.~

 

전체 코드는 다음 링크에서 확인 가능합니다 : https://github.com/dubini0/progamming_stuff/blob/main/baekjoon/%5B2%5D%20%2010000-14999/13783_hashing.py

GitHub - dubini0/progamming_stuff: programming examples