백준 15829번 Hashing (C++)

solved.ac 티어: 브론즈 2

문제 유형 : 구현, 문자열, 해싱

문제 배경 지식

1. 해싱(Hashing)이란?

- 임의의 길이와 형태를 가진 데이터를 고정된 크기의 값(해시값, hash value)으로 변환하는 과정 또는 방법이다. 이때 사용하는 변환 규칙이 해시 함수(hash function)이다.

- 해시값이 특정 배열의 인덱스라는 의미를 가지면 이를 해시 주소라고 한다.

해시 함수의 구조

해시 충돌 :  서로 다른 키가 같은 해시값을 가지는 것으로 반드시 존재하지만 해시 충돌을 줄일수록 좋은 해시 함수이다.

어디에 쓸까?

1. 빠른 데이터 검색 : O(1)으로 해시 테이블 자료형과 함께 쓰인다.

2. 고정된 길이로 변환

3. 인덱스 계산 : 1번과 일맥상통한 내용

문제 해결 소감 : 문제에서 주어진 해시함수를 그대로 구현하는 것이라서 별로 어렵지 않지만 오버플로우를 고려하지 않으면 절반만 맞게 된다.

문제 해결 전략 : 문제에서 말한 해시함수를 그대로 구현하되, 오버플로우 방지를 위해 모듈러 연산을 값이 커질 때마다 해준다.

#include <iostream>
#include <string>
int l;
long long sum;
const int M = 1234567891;
std::string str;
long long pow(int n, int i);
int main(void) {
  std::cin >> l;
  std::cin >> str;
  int i = 0;
  for (int n : str) {
    sum += (n - 96) * pow(31, i);
    sum = sum % M;

    i++;
  }
  std::cout << sum;
}

long long pow(int n, int i) {
  long long num = 1;
  for (int k = 0; k < i; k++) {
    num *= 31;
    num %= M;
  }
  return num;
}