[브론즈2]백준 15829번(Hashing) - 코테공부 29일차(2025.02.20)

문제유형

수학, 해쉬

풀이 방법 도출 과정

1. 해쉬함수: 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수

2. 이러한 해쉬 함수는 저장과 탐색에 쓰인다. 

3. 영어에는 총 26개의 알파벳이 존재하므로 a에는 1, b에는 2, c에는 3, ..., z에는 26으로 고유한 번호를 부여할 수 있다. 결과적으로 우리는 하나의 문자열을 수열로 변환할 수 있다.

4. 예를 들어서 문자열 "abba"은 수열 1, 2, 2, 1로 나타낼 수 있다. 하지만 이렇게 하면 꼬이는 게 존재한다. 모두가 겹치지 않도록 만들어야한다. 

5. 할 일은 위 식을 통해 주어진 문자열의 해시 값을 계산하는 것

 

6. 힌트 zzz의 해시 값은 26 x 31^0 + 25 x 31^1 + 26 x 31^2 = 25818

 

7. 가장 먼저 a-z까지를 숫자 1-26으로 변환하는 게 필요하다. 그렇게 하기 위해 모든 값을 매핑하는 방법을 사용하자.

3. 그리고 나서 값들을 곱하는 것을 for문으로 구현하면 된다. 또한 이를 ord함수를 사용하면 간단하게 풀수있다.

시간 복잡도

시간 복잡도는 for 문에 의해서 O(n)이다. 따라서 최악의 경우 50이므로 시간복잡도 측면에서 괜찮다.

코드 및 간단설명

ord함수를 활용하여 풀은 문제이다.

n = int(input())
str_ = list(input())
res = 0

for i in range(n):
    res += ((ord(str_[i])) - 96) * (31**i)
    
print(res % 1234567891)