[백준] 15829번 - Hashing [Java]

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

 

[백준] 15829번 - Hashing [Java]

[백준] 15829번 - Hashing [Java]

---

1.  아이디어

 

해시 함수를 직접 구현하는 문제로 힌트의 예제를 참고하면 간단한 반복문으로 구현할 수 있다.

---

2. 문제풀이

 

해시 값을 구하는 과정에서 int형 오버플로우가 발생하게 돼서 long 타입으로 선언하고 매번 모듈러 연산을 해주는 방식으로 구현했다.

---

3. 코드

 

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int L = Integer.parseInt(br.readLine());
        char[] input = br.readLine().toCharArray();

        long R = 1;
        int M = 1234567891;
        long ans = 0;

        for (char c : input) {
            ans += (c - 'a' + 1) * R;
            R *= 31;

            ans %= M;
            R %= M;
        }

        System.out.println(ans);
    }
}

---

4. 후기