백준 15829 Hashing (Java, 문자열 해시)

문제 설명

https://www.acmicpc.net/problem/15829

주어진 문자열을 해시 함수로 계산하여 숫자로 변환하는 문제입니다. 각 알파벳을 숫자로 변환하고, 특정 규칙에 따라 계산합니다.문자열의 각 문자를 다음과 같이 수로 치환합니다.

• a = 1, b = 2, ..., z = 26

아래와 같은 해시 함수를 사용합니다.

 

• r = 31
• M = 1234567891

입력

• 첫째 줄: 문자열의 길이 L (1 ≤ L ≤ 50)
• 둘째 줄: 문자열 str (영문 소문자로만 구성)

출력

• 문자열에 대해 계산한 해시 값 H

예제 입력

 

5
abcde

예제 출력

 

4739715

 

---

코드 구현

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        final int r = 31;
        final int M = 1234567891;

        Scanner sc = new Scanner(System.in);
        int L = sc.nextInt();
        String str = sc.next();

        long hash = 0;
        long pow = 1;

        for (int i = 0; i < L; i++) {
            int value = str.charAt(i) - 'a' + 1;
            hash = (hash + value * pow) % M;
            pow = (pow * r) % M;
        }

        System.out.println(hash);
    }
}

---

코드 설명

• value: 해당 문자의 숫자 값(a=1, ..., z=26)
• pow: r의 제곱을 누적해서 저장하는 변수 (r^i)
• hash: 최종 해시 값을 저장하는 변수
• 각 단계마다 mod M을 적용하여 오버플로우 방지 (a + b) % m = ((a % m) + (b % m)) % m)

---

시간 복잡도

• 반복문은 L번 수행 → O(L)