[알고리즘] CodeForce 해시 알고리즘 구현 (Python)

저번에 Python에서 set 과 list의 시간복잡도를 비교하는 글을 쓴 적이 있다.

list를 사용하는 경우 in 연산을 할 때 O(n)시간이 걸리는 반면, set은해시테이블을 기반으로 구현되기 때문에 O(1)의 시간만에 값을 찾을 수 있다는 내용이었다.

https://jjung0326.tistory.com/66

[Python] Set과 List의 시간 복잡도 차이

 

이때 사용되는 해시 알고리즘은 어떻게 구현하는지 궁금해서 직접 구현해보았다. 내가 푼 문제는 CodeForces의 다음 문제이다.

https://codeforces.com/contest/4/problem/C

Problem - C - Codeforces

문제

문제 요구사항은 다음과 같다.

n개의 사용자 이름이 주어질때, 처음 입력되는 이름이면 OK를 출력하고 생성해준다.

이미 저장된적 있는 사용자 이름인 경우, 사용자이름 뒤에 숫자(1~)를 붙여 출력하고 생성해준다.

 

이때 n값은 최대 10만개가 들어올 수 있다. 이를 만약 일반 list에 넣어 비교를 하면 O(n^2)의 시간이 걸리게 된다. 즉 100억번의 연산을 하게 되는 셈이다.

Python이 일반적으로 초당 2000만번 연산을 한다고 했을때, 문제에서 주어진 5초동안 약 1억번의 연산이 가능하므로 list에 넣어 순차비교하면 시간이 부족하다는 것을 알 수 있다.

따라서 이 문제를 해결하기 위해 해시알고리즘을 적용해보자.

---

해시 테이블 구현

해시테이블은 Key와 Value로 구성된다.

입력값이 들어오면 해시 함수를 거쳐 Key값을 얻게되고, 해당 Key값에 Value를 매핑한다.

 

n의 최대값이 10만이므로 1000/100으로 2차원배열을 생성해 저장해주었다.

또한 해시테이블에서 충돌이 발생할 때를 대비해 내부 list 칸을 100*4하여 400개로 주었다.

충돌이란?
실제로 서로 다른 값임에도 해시함수를 거쳤을 때 동일한 key 값을 가지게 되는 경우를 충돌 현상이라고 한다.
충돌을 예방하기 위한 여러 방법이 있지만, 나는 list값을 넉넉하게 주어 충돌현상을 피하고자했다.

HASH_SIZE = 1000
HASH_LEN = 400
HASH_VAL = 17   # key값이 겹치지 않게 하기 위해 주로 소수로 선언

+) HASH_VAL값은 해시함수에서 key를 얻을때 사용하는 변수인데, 최대한 충돌을 방지하기 위해 주로 소수(17, 19, 23..)로 선언한다고 한다.

 

배열 선언

필요한 list들은 다음과 같이 3가지를 선언해주었다.

index = [[0]*HASH_LEN for _ in range(HASH_SIZE)]    # 문자열이 저장된 개수를 저장
data = [[0]*HASH_LEN for _ in range(HASH_SIZE)]     # 문자열 저장
length = [0]*HASH_SIZE    # 문자열에 해당하는 Key 값이 들어온 개수를 저장

 

메인 함수

n = int(input())
for _ in range(n):
    name = input()
    key = getHashKey(name)
    cnt = checking(key, name)

    if cnt == -1:       # 해당 값이 저장된 적 없는 경우
        print("OK")
    else:               # 해당 값이 저장된 적 있는 경우
        print(f'{name}{str(cnt)}')

메인함수는 위와 같이 정의해주었다.

입력값이 들어올 때마다 getHashKey함수로 key값을 얻고, 입력값이 저장된 적 있는지 없는지 checking함수로 판단한다.

입력값이 저장된 적 없으면(-1) "OK"를 출력하고 checking함수 내에서 값을 저장한다.

입력값이 이미 저장되어있으면 뒤에 숫자가(index) 붙은 임의의 이름을 저장한다.

 

getHashKey 함수

def getHashKey(name):
    key = 0
    
    for c in name:
        key = (key*HASH_VAL) + ord(c) + HASH_VAL
        
    if key < 0:     # key가 음수이면 양수로 바꿔주기
        key = -key
        
    return key % HASH_SIZE

getHashKey함수는 해시함수라고 생각하면 된다.

입력값(name)에 대한 key값을 얻는다.

만일 키 값이 음수가 나오는 경우, 양수로 바꾸어 준다.

(key 값을 얻을 때 사용된 수식은 사용자가 임의로 지정해도 된다.)

도출된 key값을 1000이하의 수로 바꾸기 위해 나머지 연산을 수행한다.

 

checking 함수

def checking(key, name):
    key_len = length[key]   # 문자열에 해당하는 Key 값이 들어온 개수
    
    if key_len != 0:    # key 값이 들어온적 있는 경우
        for i in range(key_len):    # 들어왔던 key 값 개수만큼 돌면서
            if name == data[key][i]:    # 일치하는 값이 있으면
                index[key][i] += 1
                return index[key][i]
    
    data[key][key_len] = name   
    length[key] += 1    # 해당 key 값에 들어온 개수 +1
    return -1

해당 key값에 값이 존재하는 경우, 동일 문자열이 있는지 검사한다.

동일 문자열이 있으면, index값을 +1 해서 몇개 저장되어 있는지 반환해준다.

동일 문자열이 없는 경우, 해당 값을 저장해주고 -1을 반환한다. 

 

전체 소스코드 (Python)

HASH_SIZE = 1000
HASH_LEN = 400
HASH_VAL = 17   # key값이 겹치지 않게 하기 위해 주로 소수로 선언

index = [[0]*HASH_LEN for _ in range(HASH_SIZE)]    # 문자열이 저장된 개수를 저장
data = [[0]*HASH_LEN for _ in range(HASH_SIZE)]     # 문자열 저장
length = [0]*HASH_SIZE    # 문자열에 해당하는 Key 값이 들어온 개수를 저장

# key 값 얻기
def getHashKey(name):
    key = 0
    
    for c in name:
        key = (key*HASH_VAL) + ord(c) + HASH_VAL
        
    if key < 0:     # key가 음수이면 양수로 바꿔주기
        key = -key
        
    return key % HASH_SIZE

def checking(key, name):
    key_len = length[key]   # 문자열에 해당하는 Key 값이 들어온 개수
    
    if key_len != 0:    # key 값이 들어온적 있는 경우
        for i in range(key_len):    # 들어왔던 key 값 개수만큼 돌면서
            if name == data[key][i]:    # 일치하는 값이 있으면
                index[key][i] += 1
                return index[key][i]
    
    data[key][key_len] = name   
    length[key] += 1    # 해당 key 값에 들어온 개수 +1
    return -1

n = int(input())
for _ in range(n):
    name = input()
    key = getHashKey(name)
    cnt = checking(key, name)

    if cnt == -1:       # 해당 값이 저장된 적 없는 경우
        print("OK")
    else:               # 해당 값이 저장된 적 있는 경우
        print(f'{name}{str(cnt)}')

 

진행 예시

예를 들어 입력값이 abc(3) -> abcd(4) -> abcde(3) -> abc(3) 순서로 들어온다고 하자. 이때 괄호에 적힌 값이 해당 입력값의 key라고 가정하자.

1. "abc"가 입력된다. key값이 3이다. length[3] = 0이므로 data[3][0]에 "abc"가 저장되고, length[3] = 1이 된다. "OK"가 출력된다.

2. "abcd"가 입력된다. key값이 4다. 
length[4] = 0이므로 data[4][0]에 "abcd"가 저장되고, length[4] = 1이 된다.
 "OK"가 출력된다.

3. "abcde"가 입력된다. key값이 3이다. length[3] = 1이므로 이미 저장된 적 있는 key값이라는 의미다. 따라서 data[3]에 "abcde"가 저장되어있는지 확인한다. 
"abcde"가 저장되어있지 않으므로 data[3][1]에 "abcde"를 저장한다. length[4] = 2가 된다.

4. "abc"가 입력된다. key값이 3이다. length[3] = 2이므로 이미 저장된적 있는 key값이라는 의미다. data[3]에 "abc"가 저장되어있는지 확인한다. 첫번째 인덱스 값에 "abc"가 저장되어 있으므로 index[3][0]에 1을 더해주고 반환한다. 메인함수에서 입력값과 index값(1)을 더해 abc1을 출력한다.

---

느낀점

- 해시테이블을 쓰면서 테이블 크기가 커서 디버깅하는데 어려움을 겪었다. 출력하면서 값을 확인하는데, 출력 크기가 워낙 커서 값을 찾는데 시간이 꽤 걸렸다.

- 충돌을 피하기 위해 내부배열을 크게 주긴했지만, 이론상 동일 key값이 4개이상씩 나오게 되면 충돌현상이 발생하게 된다. 완전하게 피하려면(?) 공간복잡도가 너무 커질 것 같다는 생각이 든다. -> 이중해시 같은 방법도 있긴하다.

- 실전에서 혼자 구현하려면 연습을 많이 해봐야할것 같다. 특히 10만 n개를 1000/100으로 나누는 부분과 HASH_VAL을 사용해서 해시함수를 구현한 부분은 처음 접해봐서 익숙하지 않았다.

---

참고: 해시 테이블(Hash Table) | 👨🏻‍💻 Tech Interview (gyoogle.dev)