[백준] 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(놀랍게도 소수이다!!)로 하자.

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

풀이

문제 풀이

• 우선 알파벳 입력들이 각자 순서에 따라 숫자값으로 들어간다.

  #	알파벳 (소문자)
  1	a
  2	b
  3	c
  4	d
  5	e
  ...	...
  25	y
  26	z

• a부터 1이라면, 아스키 코드로 a = 97 이니까 문자열에서 각 문자에 -96 을 각자 해주면 a부터 1인 값으로 들어갈 것 같다.

초반 시도

• 길이 입력받고 → 알파벳 스트링 입력받고
• 저 스트링을 하나씩 쪼개서 해시맵에 넣기를 시도해봤다.
• 그러나 해시맵의 단점 = 중복값이 안들어간다.
• 그래서 zzz를 넣어도 {z=26} 이렇게 밖에 안들어가는걸 발견했다.
• 알파벳을 기억할 필요가 없기 때문에 우선 배열을 쓰는게 나을 것 같다.
  또한 계산만 진행하면 되니까 이 배열을 초반에 선언하여 저장해 둘 필요도 없을 것 같다.

코드 구현

package Hashing;

import java.util.Scanner;

public class BJ15829 {
    public static void main(String[] args) {
        final int r = 31;  // 31

        // 변수 선언
        int len;
        String str;
        int alphaIndex;
        long sum = 0;

        // 입력받기
        Scanner sc = new Scanner(System.in);
        len = sc.nextInt();     // 길이
        str = sc.next();        // 알파벳 string

        String[] strArray = str.split(""); // 입력받은 알파벳 String을 한글자씩 쪼개줘서 담아놓기

        for(int i=0; i<len; i++) {
            alphaIndex = (int)(strArray[i].charAt(0))-96;   // 알파벳의 순서 번호
            sum += alphaIndex * Math.pow(r, i);
        }

        System.out.println(sum);
    }
}

그러나 결과가 100점이 아니었다.

왜 50점이 되는지 여러 시도를 해봐도 100점을 볼 수 없었기에 정답을 구글링했다.
해답은 뒤에 있던 mod에 있었다.

• Math.pow를 쓰면 sum에 값을 더할 때 범위가 초과되는 경우가 존재했던 것이다.

• 31의 제곱수를 계산할 때 overflow 발생

• 즉, sum의 long 범위를 훨씬 초과해버렸다.

• 이를 위해서 mod 연산을 먼저 해주고 범위 안에 들어오도록 수정해야 한다.

• 따라서 문제에서 준 mod는 바로 모듈러 연산을 이용하라는 뜻이었다.

  • 모듈러 연산의 성질 중 분배법칙을 이용하면 overflow를 해결할 수 있다고 한다.
  • 주로 큰 수로 나눈 나머지를 구하라는 문제에서, 단순히 결과값에 %를 취하기 보단 연산 과정 중에서도 %를 취해야 하는 경우가 많다고 한다.

모듈러 연산 ⬇️

✔️ (A B) mod C = (A mod C B mod C) mod C

• 문제 페이지에 나와있는 수식에다 덧셈의 분배법칙을 적용하면 r의 거듭제곱과정에서 또 한번 overflow가 발생할 수 있기 때문에, 곱셈의 분배법칙도 적용해줘야 한다.

그래서 도출된 코드

final int r = 31;  // 31
final int M = 1234567891;  // 1234567891
long powValue;

powValue = (long) Math.pow(r, 0);    // powValue 초기값 == 1

for(int i=0; i<len; i++) {
    alphaIndex = (int)(strArray[i].charAt(0))-96;   // 알파벳의 순서 번호

    sum += alphaIndex * powValue % M;

    powValue = (powValue * r) % M;
		// 이전 r의 0승 값에다가 31을 계속 누적으로 곱해줘서 저장 
		// (M을 나누는건 범위 안에 들어오게하기 위해서 - 분배법칙 적용됨)
}

• 이렇게 계산이 진행된 이후 최종적으로 sum 변수인 정답을 출력하기 전에도 M을 나눠줘야한다. (위 식에서 맨 오른쪽에 있는 mod M 부분)

최종 정답 코드

package Hashing;

import java.util.Scanner;

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

        // 변수 선언
        int len;
        String str;
        int alphaIndex;
        long powValue;
        long sum = 0;

        // 입력받기
        Scanner sc = new Scanner(System.in);
        len = sc.nextInt();     // 길이
        str = sc.next();        // 알파벳 string

        String[] strArray = str.split("");      // 입력받은 알파벳 String을 한글자씩 쪼개줘서 담아놓기

        powValue = (long) Math.pow(r, 0);   // == 1

        for(int i=0; i<len; i++) {
            alphaIndex = (int)(strArray[i].charAt(0))-96;   // 알파벳의 순서 번호
            sum += alphaIndex * powValue % M;
            powValue = (powValue * r) % M;  // 이전 r의 0승 값에다가 31을 계속 누적으로 곱해줘서 저장 (M을 나누는건 범위 안에 들어오게하기 위해)
        }

        sum = sum % M;      // 모든 계산 이후 mod M 수행까지 해야 진짜 정답
        System.out.println(sum);
    }
}

참고 자료

[백준]15829.Hashing/Java
[백준] 자바 15829 Hashing
[자료구조]해싱, 해시 테이블 그리고 Java HashMap