백준 15829번 Hashing JAVA 구현해보기

---

```

백준 15829번 Hashing JAVA 구현해보기

```

이번 글을 통해 배워갈 내용

1.  백준 15829번 풀이

---

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

15829번: Hashing

 

 

 

백준 15829번 해싱은 

난이도 브론즈 등급의 문제로서

 

알파벳 소문자로 이뤄진 문자열이 주어질 때

a는 1b는 2c는 3... z는 26으로 숫자를 부여하고

r = 31, M = 1234567891으로 치환해서

각 소문자를 순서대로

 

위 공식처럼 곱해서 더해줍니다.

예를 들어 abc가 주어지면

 

(1 * 31^0 + 2 * 31^1 _ 3 * 31^2)% 1234567891

= 2946입니다.

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

값이 매우 커질 수 있기 때문에 중간중간에 모듈러 M을 해줘서 계산을 해주고

출력해주면 됩니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static final int R = 31;
    static final int M = 1234567891;

    public static void main(String[] args) throws IOException {
        // 입력
        int plainStrSize = Integer.parseInt(br.readLine());
        String plainStr = br.readLine();

        Long hashVal = 0L;
        int cnt = 0;
        for (char ch : plainStr.toCharArray()) {
            hashVal = (hashVal +(ch - 'a' + 1) * rPow(cnt)) % M;
            cnt++;
        }

        System.out.print(hashVal);
    }

    private static long rPow(int cnt) {
        long retVal = 1;
        while (cnt > 0) {
            retVal = (retVal * R) % M;
            cnt--;
        }
        return retVal;
    }
}

 

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

---