[백준] 구간성분(10840번) - 해싱

---

1. 문제

매 초마다 신호를 발생시키는 두 장치 A, B가 있다. 이 신호는 알파벳 소문자의 서열로 표현된다. A, B로부터 발생한 신호를 서열로 표시한 SA, SB의 예는 다음과 같다.

• SA = [a, f, c, d, r, d, e, s, d, c, f, w, s, z, r]
• SB = [g, e, d, s, r, d, d, e, m, z, r]

신호 서열의 어떤 구간에 포함된 문자의 종류와 개수가 순서에 상관없이 동일하면 이 두 ‘구간의 성분’은 같다고 한다. 아래에서 박스로 표시된 부분은 두 신호 SA, SB에서 성분이 같은 구간을 나타내고 있다.

즉 위의 예와 같이 성분이 같은 구간의 길이는 두 서열에서 반드시 같아야 한다. 그리고 같은 성분 의 구간은 하나 이상 존재할 수 있다. 우리는 두 신호 서열에 각각 존재하는 같은 성분 구간 중에 서 가장 긴 것을 찾으려고 한다.

 

---

30점 코드

 

str_one = input()
str_two = input()
min_l = min(map(len,[str_one,str_two]))

def partial_word(a:str,b:str):
    for i in range(min_l,0,-1):
        s_list_a = []
        for j in range(len(str_one)-i+1):
            s_list_a.append("".join(sorted(str_one[j:j+i])))
        for j in range(len(str_two)-i+1):
            if "".join(sorted(str_two[j:j+i])) in s_list_a:
                return i
    return 0

print(partial_word(str_one,str_two))

해싱의 개념을 사용하지 않고 sorted 함수를 사용하여 list에 저장 후 비교하여 길이를 찾았다.

 

이때 길이가 긴 것 부터 시작해서 저장 후 비교해서 계산 시간을 단축시키려고 코드를 구성했다.

 

---

61점 코드

str1 = input()
str2 = input()
mod = 524287

def min_l(a:str,b:str):
    if len(a) <= len(b):
        return len(a)
    else: return len(b)


def is_prime(n:int):
    i= 3
    if n %2 == 0: return False
    else:
        while i <= n**0.5:
            if n % i == 0: return False
            else: i+=2
        
        return True

def prime_list(n:int):
    l = [2]
    i = 3
    while len(l) < n:
        if is_prime(i):
            l.append(i)
            i +=2
        else: i+=2

    return l


primes = prime_list(52)

hash_list = [[] for _ in range(mod)]

def hash_val(s:str):
    value = 1
    for char in s:
        value= value*primes[ord(char)-97]
        value %= mod
    return value

def hash_val_2(s:str):
    value = 1
    for char in s:
        value= value*primes[ord(char)-71]
        value %= mod
    return value
    

def partial_word(a:str,b:str):
    for i in range(min_l(a,b),0,-1):
    
        for j in range(len(a)-i+1):
            hash_list[hash_val(a[j:j+i])].append((i,hash_val_2(a[j:j+i])))
        
        for j in range(len(b)-i+1):
            if (i,hash_val_2(b[j:j+i])) in hash_list[hash_val(b[j:j+i])]:
                return i
    
    return 0

print(partial_word(str1,str2))​

 

해싱의 개념을 도입했다.

 

a-z 까지의 소문자를 하나의 소수(primes[0:25])와 매칭했다.

 

이때 문자열의 순서가 상관이 없으므로 a-z까지 매칭된 소수의 값을 곱한 값을 큰 mod 값으로 나눈 값을 hash1으로 사용했다.

 

이때 hash collision이 일어날 수 있으므로 a-z를 primes[26:51]에  매칭해 해싱을 한 번 더 진행하고 hash2 값으로 사용했다.

 

hash_list를 mod 값의 크기만큼 만들어 준 후 hash1 주소에 (lengh, hash2)를 튜플의 형태로 저장했다.

 

그리고 str2에 대해서도 똑같이 진행 후 그 값을 hash_list 값과 대조했다.

 

---

100점 코드

 

str1 = input()
str2 = input()
mod = 524287
max_len = 0


def min_l(a:str,b:str):
    if len(a) <= len(b):
        return len(a)
    else: return len(b)


def is_prime(n:int):
    i= 3
    while i <= n**0.5:
        if n % i == 0: return False
        else: i+=2
    
    return True

def prime_list(n:int):
    l = [2]
    i = 3
    while len(l) < n:
        if is_prime(i):
            l.append(i)
            i +=2
        else: i+=2

    return l


primes = prime_list(52)

hash_list = [[] for _ in range(mod)]


for i in range(len(str1)):
    hash1 = 1
    hash2 = 1

    for j in range(i,len(str1)):
        length = j - i + 1
        hash1 *= primes[ord(str1[j])-97]
        hash1 %= mod
        hash2 *= primes[ord(str1[j])-71]
        hash2 %= mod
        
        hash_list[hash1].append((length,hash2))


for i in range(len(str2)):
    hash1 = 1
    hash2 = 1

    for j in range(i,len(str2)):
        length = j - i + 1
        hash1 *= primes[ord(str2[j])-97]
        hash1 %= mod 
        hash2 *= primes[ord(str2[j])-71]
        hash2 %= mod
        
        for hash in hash_list[hash1]:
            if hash == (length,hash2):
                max_len = max(max_len, length)

print(max_len)

 

61점과 같은 아이디어를 사용했다.

 

61점 코드는 hash_val 함수를 이용하여 hash 값을 구했다.

 

이 과정에서 불필요하게 연산 과정이 많이 일어났다.

 

예를 들면 abcde 를 hashing해 hash_list에 a ab abc abcd abcde 값을 저장한다고 했을 때

 

a, a*b, a*b*c , a*b*c*d , a*b*c*d*e 이렇게 총 1,2,3,4,5번의 곱셈 총 15번의 곱셈을 진행해야하는 반면

 

100점 코드는

a저장

a에 b 곱한 후 저장

a*b에 c 곱한 후 저장 하면서

a*b*c*d*e 총 5번만 곱하면 a, a*b, a*b*c , a*b*c*d , a*b*c*d*e 를 다 저장할 수 있었다.

 

문자열의 개수가 n개로 늘어나면 61점 코드는 곱셈 횟수가 n*(n+1)/2인 반면 100점 코드는 곱셈 횟수가 n회이다.

 

---

의문점

hash_list = [[]]*mod 일 때의 코드는 7점이 나온 반면

이 코드를 

hash_list = [ [] for _ in range(mod) ] 로 고치니 61점으로 연산 속도가 기하 급수적으로 늘어났다.