[백준] 구간성분(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점으로 연산 속도가 기하 급수적으로 늘어났다.