백준 15829 - Hashing - Java

 

백준 15829

 

문제 간단 요약

영어 소문자로 된 문자열이 주어졌을 때,
해당 문자열을 해시함수에 넣어서 생성된 해시값을 출력하라.

문제 해석

문제를 잘 이해했는지 확인하는 구현 문제
해사함수에 대해 공부해봤으면 하는 출제자의 의도와 노력이 보인다.

문제 풀이

1. 각 자리의 소문자를 정수(1~26)으로 치환한다.
2. 각 자리에 해당하는 만큼 r(31)을 거듭제곱한 후 치환한 값에 곱한다.
3. M(1234567891)으로 나머지 연산을 한다.

막힌 부분 : 50점

• r^i(31^i)는 거듭제곱이기 때문에, L이 클 때 굉장히 커진다.
• 이거 어떻게 처리할지?

해결방법

• 내가 해결한 방법
  • r에 31을 곱할 때마다 M을 사용한 나머지 연산을 통해 범위를 줄인다.
  • 추가 문제 : 나머지 연산을 통해 범위를 줄여도 M은 약 12억   ➡  a의 값이 2이상이면 21억(=int의 범위)를 초과한다.
    • 때문에 r과 result는 long으로 선언해준다.
• 다른 방법
  • 그냥 BigInteger 클래스를 사용하면 된다.
• BigInteger를 사용하지 않은 이유
  • 50점에서 버그를 찾고 수정하는 과정에 집중하다보니 Biginteger를 못 떠올렸다.
  • BigInteger는 연산량이 많아서 웬만하면 안 쓰려고 하다보니 아예 선택지에서 제외를 시켜버렸다.

풀면서 알게 된 것 / 느낀 것 

1. mod라는 기호는 %(나머지)연산을 뜻한다.
2. 자주 쓰이는 해시 함수
3. 언제가 변수 범위는 주의해야 한다.
4. BigInteger를 안써버릇 한다고 선택지에서 제외시키는 실수를 했다. 고쳐야 할 부분이다.

제출코드

import java.util.Scanner;

class Main {
    public static void main(String args[])  {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        String string = sc.next();
        long result = 0;
        for (int i = 0; i < n; i++) {

            // 1. 치환
            int a = string.charAt(i) - 'a' + 1;

            // 2. 거듭제곱 + 곱하기
            long r = 1;
            for (int j = 0; j < i; j++) {
                r = r * 31 % 1234567891;
            }
            result += a * r;

            // 3. 나머지 연산
            result %= 1234567891;
        }

        System.out.println(result);
    }
}