[백준] 15829 - Hashing JAVA

Solved.ac Class 완전정복 프로젝트

Class : 2 ~ 2 ++

 

 

---

링크

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

15829번: Hashing

 

문제

APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정의한다. 해시 함수는 무궁무진한 응용 분야를 갖는데, 대표적으로 자료의 저장과 탐색에 쓰인다.

이 문제에서는 여러분이 앞으로 유용하게 쓸 수 있는 해시 함수를 하나 가르쳐주고자 한다. 먼저, 편의상 입력으로 들어오는 문자열에는 영문 소문자(a, b,..., z)로만 구성되어있다고 가정하자. 영어에는 총 26개의 알파벳이 존재하므로 a에는 1, b에는 2, c에는 3, ..., z에는 26으로 고유한 번호를 부여할 수 있다. 결과적으로 우리는 하나의 문자열을 수열로 변환할 수 있다. 예를 들어서 문자열 "abba"은 수열 1, 2, 2, 1로 나타낼 수 있다.

해시 값을 계산하기 위해서 우리는 문자열 혹은 수열을 하나의 정수로 치환하려고 한다. 간단하게는 수열의 값을 모두 더할 수도 있다. 해시 함수의 정의에서 유한한 범위의 출력을 가져야 한다고 했으니까 적당히 큰 수 M으로 나눠주자. 짜잔! 해시 함수가 완성되었다. 이를 수식으로 표현하면 아래와 같다.

 

해시 함수의 입력으로 들어올 수 있는 문자열의 종류는 무한하지만 출력 범위는 정해져 있다.. 다들 비둘기 집의 원리에 대해서는 한 번쯤 들어봤을 것이다. 그 원리에 의하면 서로 다른 문자열이더라도 동일한 해시 값을 가질 수 있다. 이를 해시 충돌이라고 하는데, 좋은 해시 함수는 최대한 충돌이 적게 일어나야 한다. 위에서 정의한 해시 함수는 알파벳의 순서만 바꿔도 충돌이 일어나기 때문에 나쁜 해시 함수이다. 그러니까 조금 더 개선해보자.

어떻게 하면 순서가 달라졌을 때 출력 값도 달라지게 할 수 있을까? 머리를 굴리면 수열의 각 항마다 고유한 계수를 부여하면 된다는 아이디어를 생각해볼 수 있다. 가장 대표적인 방법은 항의 번호에 해당하는 만큼 특정한 숫자를 거듭제곱해서 곱해준 다음 더하는 것이 있다. 이를 수식으로 표현하면 아래와 같다.

보통 r과 M은 서로소인 숫자로 정하는 것이 일반적이다. 우리가 직접 정하라고 하면 힘들테니까 r의 값은 26보다 큰 소수인 31로 하고 M의 값은 1234567891(놀랍게도 소수이다!!)로 하자.

이제 여러분이 할 일은 위 식을 통해 주어진 문자열의 해시 값을 계산하는 것이다. 그리고 이 함수는 간단해 보여도 자주 쓰이니까 기억해뒀다가 잘 써먹도록 하자.

 

 

Small (50점)
1 ≤ L ≤ 5
Large (50점)
1 ≤ L ≤ 50

 

 

접근방법

 소문자 입력에 대하여 올바른 해시값을 도출해낼 수 있는지에 대한 문제이다. 여기서 r의 지수 값은 자릿수와 같으므로, 길이가 길어질 때마다 오버플로우가 발생할 수 있다는 사실을 염두에 두고, 푸는 것이 포인트다. 여기까지 인지하고 풀이로 들어가자.

 

 

실패 원인

 나는 이 문제를 꽤 많이 반타작(small만 정답) 했다. 이유는 간단하다. double 형을 사용한다고 해도, 31의 49승은 가뿐히 오버플로우에 도달한다. 50번째 자리만 해도 이렇게 값이 큰데 1번째 자리부터 합을 구하려 하니 당연히 오버플로우가 날 수밖에 없다.  아래의 그래프를 보자.

 

 계열 2 ~ 계열 7 은 a ~ f까지의 알파벳이며, x축은 각 자릿수를 의미한다. (누적된 값이 아니라 각 자리의 값만 해도 저렇다.) y축의 값을 보면, 이미 정신이 나간다.  f가 6번째 자리에 있을 때, 값은 48190861056이다.  그렇기 때문에 자료형만 바꾸는 것은 답이 아니다. 그럼 어떻게 해야 할까 

 

 

풀이

 r이 자릿수마다 기하급수적으로 진화하기 때문에 나머지의 특징을 이용할 것이다.  특징은 예시를 들어 설명한다.

 

 

[제곱을 구한 뒤 나머지를 찾는 경우]

7의 3 제곱은 343이다. 7의 3 제곱을 5로 나누었을 때 값은 3이다.

 

7*7*7 % = 3

 

 

[나머지를 찾아가며 제곱을 하는 경우]

이번에는 각 지수마다 한 번씩 나머지를 구한 뒤 곱을 한 결과이다.

7 % 5 = 2

2 * 7 % = 4

4 * 7 % = 3

 

 

 보시다시피, 똑같다. 이유는 곱의 형태이기 때문에 나머지가 달라질 수가 없다. 이러한 나머지의 특징을 이용해서, 최대한 숫자를 줄여 계산하면 된다.

 

코드

import java.util.Scanner;

public class Main {

    private static final int r = 31;
    private static final int M = 1234567891;


    public static void main(String[] args) {
        Main test = new Main();
    }

    public Main(){
        Scanner sc = new Scanner(System.in);
        sc.nextLine();
        String datas = sc.nextLine();

        System.out.println(solution(datas));
    }

    public long solution(String datas) {
        //output용 변수
        long result = 0;
        //지수
        int coefficient = 0;
        
        for (char data : datas.toCharArray()) {
            //'a'를 1로 기준잡는다.
            long tmp = data - 96;
            
            //곱할때 마다 나머지를 구해 값을 줄인다.
            for (int i = 0; i < coefficient; i++) {
                tmp *= r;
                tmp %= M;
            }
            result +=tmp;
            //분배의 법칙
            result %= M;
            
            //지수 증가
            coefficient++;
        }

        return result;
    }

  
}

 

 

 

 

결과

 

 

 

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.